Submission #826150
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
// memory: O(Q loglogN logN)
// mutable_get: O(loglogN logN)
// immutable_get: O(loglogN)
template<class T>
class Array {
public:
Array() {}
Array(int n) {
h = 0;
for (int i = 1; i < n; i *= 16) h += 4;
}
T *mutable_get(int k) {
auto p = mutable_get(k, root, 0, h);
root = p.first;
return &p.second->value;
}
T immutable_get(int k) {
return immutable_get(k, root, 0, h)->value;
}
private:
struct node {
node *ch[16] = {};
T value;
node() {}
node(T value) : value(value) {}
};
int h;
node *root = nullptr;
node *immutable_get(int a, node *x, int l, int d) {
if (d == 0) return x;
int id = (a - l) >> (d - 4);
return immutable_get(a, x->ch[id], l + (id << (d - 4)), d - 4);
}
pair<node *, node *> mutable_get(int a, node *x, int l, int d) {
x = x != nullptr ? new node(*x) : new node();
if (d == 0) return make_pair(x, x);
int id = (a - l) >> (d - 4);
auto p = mutable_get(a, x->ch[id], l + (id << (d - 4)), d - 4);
x->ch[id] = p.first;
return make_pair(x, p.second);
}
};
// root: O(logN loglogN)
// merge: O(logN loglogN)
struct UnionFind {
struct node {
int parent;
int size;
};
Array<node> uf;
UnionFind() : uf(0) {}
UnionFind(int n) : uf(n) {
for (int i = 0; i < n; i++) {
node *nd = uf.mutable_get(i);
nd->parent = i;
nd->size = 1;
}
}
int root(int x) {
node nd = uf.immutable_get(x);
if (nd.parent == x) return x;
return root(nd.parent);
}
UnionFind merge(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return *this;
node *u = uf.mutable_get(x);
node *v = uf.mutable_get(y);
u->parent = v->parent = u->size > v->size ? x : y;
u->size = v->size = u->size + v->size;
return *this;
}
int query(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
return uf.immutable_get(x).size + uf.immutable_get(y).size;
} else {
return uf.immutable_get(x).size;
}
}
};
int main() {
int n, m;
cin >> n >> m;
vector<UnionFind> his(m + 1);
UnionFind uf(n);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--;
b--;
uf.merge(a, b);
his[i + 1] = uf;
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
x--;
y--;
int pass = m, fail = 0;
while (pass - fail > 1) {
int mid = (pass + fail) / 2;
if (his[mid].query(x, y) >= z) {
pass = mid;
} else {
fail = mid;
}
}
printf("%d\n", pass);
}
}
Submission Info
Submission Time |
|
Task |
D - Stamp Rally |
User |
pekempey |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
2623 Byte |
Status |
AC |
Exec Time |
1657 ms |
Memory |
255616 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:114:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
^
./Main.cpp:125:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &x, &y, &z);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt |
All |
0_00.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
4 ms |
256 KB |
1_00.txt |
AC |
1066 ms |
255488 KB |
1_01.txt |
AC |
1289 ms |
255488 KB |
1_02.txt |
AC |
1302 ms |
255488 KB |
1_03.txt |
AC |
1292 ms |
255488 KB |
1_04.txt |
AC |
1280 ms |
255488 KB |
1_05.txt |
AC |
1324 ms |
255488 KB |
1_06.txt |
AC |
1337 ms |
255488 KB |
1_07.txt |
AC |
1399 ms |
255488 KB |
1_08.txt |
AC |
1461 ms |
255616 KB |
1_09.txt |
AC |
1433 ms |
255488 KB |
1_10.txt |
AC |
1425 ms |
255488 KB |
1_11.txt |
AC |
1454 ms |
255488 KB |
1_12.txt |
AC |
1473 ms |
255488 KB |
1_13.txt |
AC |
1560 ms |
255488 KB |
1_14.txt |
AC |
1400 ms |
255488 KB |
1_15.txt |
AC |
1178 ms |
255488 KB |
1_16.txt |
AC |
1541 ms |
249216 KB |
1_17.txt |
AC |
1628 ms |
248832 KB |
1_18.txt |
AC |
1590 ms |
246272 KB |
1_19.txt |
AC |
1541 ms |
255488 KB |
1_20.txt |
AC |
1612 ms |
233472 KB |
1_21.txt |
AC |
1605 ms |
253056 KB |
1_22.txt |
AC |
1621 ms |
244992 KB |
1_23.txt |
AC |
1626 ms |
244352 KB |
1_24.txt |
AC |
1601 ms |
230528 KB |
1_25.txt |
AC |
1657 ms |
247680 KB |
1_26.txt |
AC |
1532 ms |
237952 KB |
1_27.txt |
AC |
1576 ms |
248320 KB |
1_28.txt |
AC |
1566 ms |
247168 KB |
1_29.txt |
AC |
1572 ms |
230784 KB |
1_30.txt |
AC |
1612 ms |
245888 KB |
1_31.txt |
AC |
1522 ms |
233472 KB |