Submission #137508

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<complex>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define sz(x) (int)(x).size()
#define popcount __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<int,P> Q;
typedef vector<int> vi;

const int MX = 2005, INF = 1000000000;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;
const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; //<^>v

int n, m, q;
int e[MX][MX];
int g[MX];

vector<Q> ge[MX];

// Union find
struct uf{
	vector<int> d;
	uf(){}
	uf(int sz):d(sz,-1){}
	void init(){
		rep(i,sz(d)) d[i] = -1;
	}
	int root(int x){
		if(d[x] < 0) return x;
		return d[x] = root(d[x]);
	}
	void unite(int x, int y){
		x = root(x); y = root(y);
		if(x == y) return;
		if(d[x] > d[y]) swap(x,y);
		if(d[x] == d[y]) d[x]--;
		d[y] = x;
	}
};
//

int main(){
	scanf("%d%d",&n,&m);
	int a, b, c;
	rep(i,m){
		scanf("%d%d%d",&a,&b,&c);
		e[a][b] = e[b][a] = c;
	}
	rep(i,n) g[i] = i;
	uf t(n+5);
	
	scanf("%d",&q);
	rep(qi,q){
		scanf("%d%d",&a,&b);
		a = g[a];
		b = g[b];
		vi x, y;
		
		rep(i,n) if(g[i] == a) x.pb(i);
		rep(i,n) if(g[i] == b) y.pb(i);
		
		vector<Q> p;
		rep(i,sz(x))rep(j,sz(y)){
			if(e[x[i]][y[j]]) p.pb(Q(e[x[i]][y[j]],P(x[i],y[j])));
		}
		rep(i,sz(ge[a])) p.pb(ge[a][i]);
		rep(i,sz(ge[b])) p.pb(ge[b][i]);
		t.init();
		ge[a].clear();
		ge[b].clear();
		sort(rng(p));
		
		int cnt = sz(x)+sz(y)-1;
		int ans = 0;
		rep(i,sz(p)){
			c = p[i].fi;
			int v = p[i].se.fi;
			int u = p[i].se.se;
			if(t.root(v) != t.root(u)){
				ans += c;
				t.unite(v,u);
				ge[a].pb(p[i]);
				--cnt;
			}
		}
		rep(i,n) if(g[i] == b) g[i] = a;
		if(cnt){
			puts("IMPOSSIBLE");
		} else {
			printf("%d\n",ans);
		}
		//cout << sz(x) << endl;
		//cout << sz(y) << endl;
	}
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:71:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:74:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:80:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:82:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result