Submission #3013441


Source Code Expand

#include<map>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;

long long const MAX = 100003;

class unionfind {
private:
	int par[MAX]; int rank[MAX];
public:
	unionfind(long long n) {
		for (long long i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}
	int find(long long x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}
	bool same(long long x, long long y) {
		return find(x) == find(y);
	}
	void unite(long long x, long long y) {
		if (!same(x, y)) {
			x = par[x]; y = par[y];
			if (rank[x] < rank[y]) {
				par[x] = y;
			}
			else {
				par[y] = x;
				if (rank[x] == rank[y]) {
					rank[x]++;
				}
			}
		}
	}
};

ll parent[MAX];
ll turn[MAX];
ll depth[MAX];

struct edge {
	ll from; ll to; ll cost;
};

vector<edge> G[MAX];
ll doubling[MAX][30];
ll biggest[MAX][50];


void make_tree(ll n) {
	REP(i, 1, n) {
		parent[i] = -1;
		turn[i] = -1;
	}
	REP(i, 1, n) {
		if (parent[i] == -1) {
			parent[i] = i;
			depth[i] = 0;
			queue<ll> qu;
			qu.push(i);
			while (!qu.empty()) {
				ll cur = qu.front();
				qu.pop();
				for (ll j = 0; j < G[cur].size(); j++) {
					ll next = G[cur][j].to;
					if (parent[next] == -1) {
						parent[next] = cur;
						turn[next] = G[cur][j].cost;
						depth[next] = depth[cur] + 1;
						qu.push(next);
					}
				}
			}
		}
	}
	REP(i, 1, n) {
		doubling[i][0] = parent[i];
		biggest[i][0] = turn[i];
		REP(j, 1, 25) {
			doubling[i][j] = doubling[doubling[i][j - 1]][j - 1];
			biggest[i][j] = max(biggest[i][j - 1], biggest[doubling[i][j - 1]][j - 1]);
		}
	}
}

ll get_anc(ll x, ll y, ll& cos) {
	for (ll i = 0; (1 << i) <= y; i++) {
		if ((1 << i)&y != 0) {
			cos = max(cos, biggest[x][i]);
			x = doubling[x][i];
		}
	}
	return x;
}

ll get_lca(ll x, ll y, ll& cos) {
	if (depth[x] < depth[y]) {
		swap(x, y);
	}
	x = get_anc(x, depth[x] - depth[y], cos);
	if (x == y) {
		return x;
	}
	for (ll i = 25; i >= 0; i--) {
		if (doubling[x][i] != doubling[y][i]) {
			cos = max(cos, max(biggest[x][i], biggest[y][i]));
			x = doubling[x][i];
			y = doubling[y][i];
		}
	}
	cos = max(cos, max(turn[x], turn[y]));
	return parent[x];
}

int main() {
	ll n, m;
	cin >> n >> m;
	unionfind un(n+1);

	REP(i, 1, m) {
		ll a, b;
		cin >> a >> b;
		if (!un.same(a, b)) {
			un.unite(a, b);
			G[a].push_back({ a,b,i });
			G[b].push_back({ b,a,i });
		}
	}
	make_tree(n);
	ll qqq;
	cin >> qqq;
	REP(iii, 1, qqq) {
		ll x, y;
		cin >> x >> y;
		if (doubling[x][25]!=doubling[y][25]) {
			cout << -1 <<endl;
		}
		else {
			ll cnt = -1;
			get_lca(x, y, cnt);
			cout << cnt << endl;
		}
	}
	/*
	REP(i,1,n) cout << parent[i] << " ";
	cout << endl;
	REP(i, 1, n) {
		REP(j, 0, 6) {
			cout << biggest[i][j] << " ";
		}
		cout << endl;
	}
	*/
}

Submission Info

Submission Time
Task H - Union Sets
User nejineji
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3021 Byte
Status WA
Exec Time 402 ms
Memory 79336 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 32
WA × 17
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 3 ms 6400 KB
sample_02.txt AC 3 ms 6400 KB
sample_03.txt AC 3 ms 6400 KB
subtask_1_1.txt AC 3 ms 6400 KB
subtask_1_10.txt WA 25 ms 6400 KB
subtask_1_11.txt WA 172 ms 7808 KB
subtask_1_12.txt AC 28 ms 38272 KB
subtask_1_13.txt WA 5 ms 6400 KB
subtask_1_14.txt AC 3 ms 6400 KB
subtask_1_15.txt WA 63 ms 6784 KB
subtask_1_16.txt WA 6 ms 6400 KB
subtask_1_17.txt AC 18 ms 6400 KB
subtask_1_18.txt WA 3 ms 6400 KB
subtask_1_19.txt AC 24 ms 32384 KB
subtask_1_2.txt AC 3 ms 6400 KB
subtask_1_20.txt WA 3 ms 6400 KB
subtask_1_21.txt WA 12 ms 6400 KB
subtask_1_22.txt AC 15 ms 21376 KB
subtask_1_23.txt AC 278 ms 68480 KB
subtask_1_24.txt AC 267 ms 68480 KB
subtask_1_25.txt AC 273 ms 68608 KB
subtask_1_26.txt WA 279 ms 69120 KB
subtask_1_27.txt WA 375 ms 75520 KB
subtask_1_28.txt WA 377 ms 75520 KB
subtask_1_29.txt AC 270 ms 68480 KB
subtask_1_3.txt AC 3 ms 6400 KB
subtask_1_30.txt AC 268 ms 68480 KB
subtask_1_31.txt AC 272 ms 68608 KB
subtask_1_32.txt AC 269 ms 69120 KB
subtask_1_33.txt WA 398 ms 75392 KB
subtask_1_34.txt WA 402 ms 75520 KB
subtask_1_35.txt AC 273 ms 68480 KB
subtask_1_36.txt AC 277 ms 68480 KB
subtask_1_37.txt AC 269 ms 68608 KB
subtask_1_38.txt AC 273 ms 69180 KB
subtask_1_39.txt AC 324 ms 75056 KB
subtask_1_4.txt AC 42 ms 53760 KB
subtask_1_40.txt AC 325 ms 75056 KB
subtask_1_41.txt AC 194 ms 6656 KB
subtask_1_42.txt WA 203 ms 6656 KB
subtask_1_43.txt WA 339 ms 56320 KB
subtask_1_44.txt WA 380 ms 79336 KB
subtask_1_45.txt AC 192 ms 6656 KB
subtask_1_46.txt AC 269 ms 68480 KB
subtask_1_5.txt WA 25 ms 6400 KB
subtask_1_6.txt AC 28 ms 38272 KB
subtask_1_7.txt AC 6 ms 10624 KB
subtask_1_8.txt AC 9 ms 14848 KB
subtask_1_9.txt AC 44 ms 12800 KB