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 |
|
|
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 |