Submission #996578


Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repv(t,it,v) for(vector<t>::iterator it = v.begin() ; it != v.end() ; ++it)

const int UF_MAX = 1000000;

class UF{
	int x[UF_MAX];
	
public:
	
	UF(){
		for(int i = 0 ; i < UF_MAX ; ++i) x[i] = -1;
	}
	
	int boss(int a){
		int s = a;
		while(x[s] > -1) s = x[s];
		if(s != a) x[a] = s;
		return s;
	}
	
	void uni(int a , int b){
		int s = boss(a);
		int t = boss(b);
		if(s != t){
			if(x[s] < x[t]){
				x[s] += x[t];
				x[t] = s;
			} else {
				x[t] += x[s];
				x[s] = t;
			}
		}
	}
	
	bool find(int a , int b){
		return boss(a) == boss(b);
	}
	
	int count(int a){
		int b = 0;
		for(int i = 0 ; i < a ; ++i) if(x[i] < 0) ++b;
		return b;
	}
} uf;

int N,M,Q;
vector<P2> V[4004];
vector<P3> E;
int d[4004];
int p[4004];
int q[4004];

void dfs(int a){
	repv(P2,it,V[a]){
		if(d[(*it).second] < 0){
			d[(*it).second] = d[a] + 1;
			p[(*it).second] = a;
			q[(*it).second] = (*it).first;
			dfs((*it).second);
		}
	}
}

int main(){
	scanf("%d%d" , &N , &M);
	repp(i,0,M){
		int a,b,c;
		scanf("%d%d%d" , &a , &b , &c);
		E.PB(M3P(c,a,b));
	}
	sort(E.begin(),E.end());
	int w = 0;
	repp(i,0,M){
		int x = E[i].first.second;
		int y = E[i].second;
		if(!uf.find(x,y)){
			uf.uni(x,y);
			V[x].PB(MP(E[i].first.first,y));
			V[y].PB(MP(E[i].first.first,x));
			w += E[i].first.first;
		}
	}
	fill(d,d+N+1,-1);
	fill(p,p+N+1,-1);
	fill(q,q+N+1,0);
	d[1] = 0;
	dfs(1);
	scanf("%d" , &Q);
	repp(i,0,Q){
		int s,t;
		scanf("%d%d" , &s , &t);
		int ans = 0;
		while(s != t){
			if(d[s] > d[t]){
				ans = max(ans , q[s]);
				s = p[s];
			} else {
				ans = max(ans , q[t]);
				t = p[t];
			}
		}
		printf("%d\n" , w - ans);
	}
	return 0;
}

Submission Info

Submission Time
Task A - Graph
User PIandS
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2409 Byte
Status WA
Exec Time 194 ms
Memory 10608 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:86:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &N , &M);
                         ^
./Main.cpp:89:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &a , &b , &c);
                                 ^
./Main.cpp:109:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &Q);
                  ^
./Main.cpp:112:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &s , &t);
                          ^

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 300 0 / 200
Status
AC × 2
AC × 2
WA × 10
AC × 3
WA × 18
AC × 3
WA × 26
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 6 ms 4224 KB
sample_2.txt AC 6 ms 4224 KB
subtask_1_1.txt WA 7 ms 4224 KB
subtask_1_10.txt WA 79 ms 7412 KB
subtask_1_11.txt AC 6 ms 4224 KB
subtask_1_2.txt WA 21 ms 5244 KB
subtask_1_3.txt WA 153 ms 10480 KB
subtask_1_4.txt WA 8 ms 4480 KB
subtask_1_5.txt WA 9 ms 4480 KB
subtask_1_6.txt WA 43 ms 5880 KB
subtask_1_7.txt WA 152 ms 10480 KB
subtask_1_8.txt WA 9 ms 4480 KB
subtask_1_9.txt WA 11 ms 4544 KB
subtask_2_1.txt WA 154 ms 10480 KB
subtask_2_2.txt WA 154 ms 10480 KB
subtask_2_3.txt WA 154 ms 10480 KB
subtask_2_4.txt WA 154 ms 10608 KB
subtask_2_5.txt WA 10 ms 4480 KB
subtask_2_6.txt WA 16 ms 4800 KB
subtask_2_7.txt WA 44 ms 6008 KB
subtask_2_8.txt WA 154 ms 10480 KB
subtask_3_1.txt WA 193 ms 10480 KB
subtask_3_2.txt WA 193 ms 10480 KB
subtask_3_3.txt WA 42 ms 5632 KB
subtask_3_4.txt WA 49 ms 5696 KB
subtask_3_5.txt WA 120 ms 7792 KB
subtask_3_6.txt WA 160 ms 10480 KB
subtask_3_7.txt WA 194 ms 10480 KB
subtask_3_8.txt WA 193 ms 10480 KB