# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
405215 |
2021-05-16T00:44:21 Z |
gevacrt |
Bridges (APIO19_bridges) |
C++17 |
|
3000 ms |
274200 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
struct DISJOINT_SET_UNION {
vi par, sz; int groups;
void init(int N){
par.resize(N), sz.resize(N, 1);
for(int x = 0; x < N; x++) par[x] = x;
groups = N;
}
int parent(int x){
if(par[x] == x) return x;
return parent(par[x]);
}
void merge(int x, int y){
x = parent(x), y = parent(y);
if(x == y) return;
if(sz[x] > sz[y]) swap(x, y);
par[x] = y; sz[y] += sz[x];
groups--;
}
void unmerge(int x, int y){
if(sz[x] > sz[y]) swap(x, y);
par[x] = x; sz[y] -= sz[x];
groups++;
}
};
const int BLOCK = 400;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, M; cin >> N >> M;
vector<array<int, 3>> E(M+1); // {u, v, d}
vi last_changed(M+1);
for(int x = 1; x <= M; x++){
cin >> E[x][0] >> E[x][1] >> E[x][2];
}
vector<array<int, 3>> QRY; // {weight, start, time}
vector<array<int, 4>> UPD; // {d, l, r, x}
int Q; cin >> Q;
for(int t = 1; t <= Q; t++){
int c; cin >> c;
if(c == 1){
int i, d; cin >> i >> d;
UPD.push_back({E[i][2], last_changed[i], t-1, i});
last_changed[i] = t; E[i][2] = d;
}else{
int s, w; cin >> s >> w;
QRY.push_back({w, s, t});
}
}
for(int x = 1; x <= M; x++){
UPD.push_back({E[x][2], last_changed[x], Q, x});
}
sort(all(QRY)); sort(all(UPD));
reverse(all(QRY));
DISJOINT_SET_UNION DSU[BLOCK];
for(auto &i : DSU) i.init(N+1);
vvi jp(Q+10); vi ans(Q+10, -1);
auto upd = [&](int l, int r, int x){
for(; l <= r; ){
if(l%BLOCK == 0 and l+BLOCK-1 <= r){
DSU[l/BLOCK].merge(E[x][0], E[x][1]);
l += BLOCK;
}else{
jp[l].push_back(x); l++;
}
}
};
for(auto [weight, start, time] : QRY){
while(!UPD.empty() and UPD.back()[0] >= weight){
upd(UPD.back()[1], UPD.back()[2], UPD.back()[3]);
UPD.pop_back();
}
// dsu with rollbacks
vii rollback; auto &BOB = DSU[time/BLOCK];
for(auto i : jp[time]){
auto [u, v, _] = E[i];
u = BOB.parent(u), v = BOB.parent(v);
if(u == v) continue;
BOB.merge(u, v); rollback.push_back({u, v});
}
ans[time] = BOB.sz[BOB.parent(start)];
reverse(all(rollback));
for(auto [u, v] : rollback)
BOB.unmerge(u, v);
}
for(auto i : ans)
if(i != -1) cout << i << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
41 ms |
12100 KB |
Output is correct |
4 |
Correct |
6 ms |
908 KB |
Output is correct |
5 |
Correct |
23 ms |
6512 KB |
Output is correct |
6 |
Correct |
22 ms |
6320 KB |
Output is correct |
7 |
Correct |
28 ms |
6724 KB |
Output is correct |
8 |
Correct |
26 ms |
6732 KB |
Output is correct |
9 |
Correct |
36 ms |
6672 KB |
Output is correct |
10 |
Correct |
28 ms |
6732 KB |
Output is correct |
11 |
Correct |
27 ms |
6680 KB |
Output is correct |
12 |
Correct |
29 ms |
6676 KB |
Output is correct |
13 |
Correct |
33 ms |
6784 KB |
Output is correct |
14 |
Correct |
30 ms |
6724 KB |
Output is correct |
15 |
Correct |
30 ms |
6708 KB |
Output is correct |
16 |
Correct |
29 ms |
6552 KB |
Output is correct |
17 |
Correct |
27 ms |
6732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3055 ms |
274200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3061 ms |
219456 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3079 ms |
168168 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3055 ms |
274200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
41 ms |
12100 KB |
Output is correct |
4 |
Correct |
6 ms |
908 KB |
Output is correct |
5 |
Correct |
23 ms |
6512 KB |
Output is correct |
6 |
Correct |
22 ms |
6320 KB |
Output is correct |
7 |
Correct |
28 ms |
6724 KB |
Output is correct |
8 |
Correct |
26 ms |
6732 KB |
Output is correct |
9 |
Correct |
36 ms |
6672 KB |
Output is correct |
10 |
Correct |
28 ms |
6732 KB |
Output is correct |
11 |
Correct |
27 ms |
6680 KB |
Output is correct |
12 |
Correct |
29 ms |
6676 KB |
Output is correct |
13 |
Correct |
33 ms |
6784 KB |
Output is correct |
14 |
Correct |
30 ms |
6724 KB |
Output is correct |
15 |
Correct |
30 ms |
6708 KB |
Output is correct |
16 |
Correct |
29 ms |
6552 KB |
Output is correct |
17 |
Correct |
27 ms |
6732 KB |
Output is correct |
18 |
Execution timed out |
3055 ms |
274200 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |