# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
681579 |
2023-01-13T11:53:30 Z |
79brue |
Bridges (APIO19_bridges) |
C++17 |
|
2685 ms |
11120 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int G = 320;
struct UnionFind{
int n;
int par[50002], sz[50002];
vector<pair<int, int> > stk;
void init(int _n){
n = _n;
for(int i=1; i<=n; i++) par[i] = i, sz[i] = 1;
stk.clear();
}
int find(int x){
if(par[x] == x) return x;
return find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x==y) return;
if(sz[x] > sz[y]) swap(x, y);
stk.push_back(make_pair(-y, sz[y]));
stk.push_back(make_pair(x, par[x]));
par[x] = y;
sz[y] += sz[x];
}
void rollback(){
while(!stk.empty()){
auto p = stk.back();
stk.pop_back();
if(p.first < 0) sz[-p.first] = p.second;
else par[p.first] = p.second;
}
}
void check(){
stk.clear();
}
} dsu;
struct Edge{
int x, y, w, idx;
Edge(int x, int y, int w, int idx): x(x), y(y), w(w), idx(idx){}
bool operator<(const Edge &r)const{
return w>r.w;
}
};
int n, m, q;
vector<Edge> edgeVec;
int ex[100002], ey[100002], weight[100002];
int qt[100002], qa[100002], qb[100002];
int ans[100002];
void solve(int L, int R);
int main(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
ex[i] = x, ey[i] = y, weight[i] = w;
edgeVec.push_back(Edge(x, y, w, i));
}
sort(edgeVec.begin(), edgeVec.end());
scanf("%d", &q);
for(int i=1; i<=q; i++){
scanf("%d %d %d", &qt[i], &qa[i], &qb[i]);
}
for(int d=1; d<=q; d+=G){
solve(d, min(q, d+G-1));
}
for(int i=1; i<=q; i++) if(qt[i]==2) printf("%d\n", ans[i]);
}
bool edgeUsed[100002];
struct dat{
int x, w, idx;
dat(){}
dat(int x, int w, int idx): x(x), w(w), idx(idx){}
bool operator<(const dat &r)const{
return w>r.w;
}
};
int edgeIdx[100002];
int matrix[500][500]; /// matrix[i][j]: i번 간선의 쿼리 시점 j에서의 가중치
vector<int> usedEdges;
int S;
void solve(int L, int R){ /// L~R번 쿼리를 처리
for(auto &p: edgeVec) p.w = weight[p.idx];
sort(edgeVec.begin(), edgeVec.end());
vector<dat> queryVec;
usedEdges.clear();
for(int i=L; i<=R; i++){
if(qt[i] == 1) edgeUsed[qa[i]] = 1, usedEdges.push_back(qa[i]);
else queryVec.push_back(dat(qa[i], qb[i], i));
}
sort(queryVec.begin(), queryVec.end());
dsu.init(n);
/// matrix를 채우고 각 시점에서 가중치에 대한 정보를 얻자
sort(usedEdges.begin(), usedEdges.end());
usedEdges.erase(unique(usedEdges.begin(), usedEdges.end()), usedEdges.end());
S = (int)usedEdges.size();
for(int i=0; i<S; i++){
int x = usedEdges[i];
edgeIdx[x] = i;
matrix[i][0] = weight[x];
for(int j=L; j<=R; j++){
if(qt[j] == 1 && qa[j] == x) matrix[i][j-L] = qb[j];
else if(j>L) matrix[i][j-L] = matrix[i][j-L-1];
}
}
int pnt = 0;
for(dat p: queryVec){
while(pnt < (int)edgeVec.size() && edgeVec[pnt].w >= p.w){
if(!edgeUsed[edgeVec[pnt].idx]) dsu.merge(edgeVec[pnt].x, edgeVec[pnt].y);
pnt++;
}
dsu.check();
for(int e: usedEdges){
if(matrix[edgeIdx[e]][p.idx-L] < p.w) continue;
dsu.merge(ex[e], ey[e]);
}
ans[p.idx] = dsu.sz[dsu.find(p.x)];
dsu.rollback();
}
/// weight 배열 업데이트
for(int i=L; i<=R; i++) if(qt[i] == 1) weight[qa[i]] = qb[i], edgeUsed[qa[i]] = 0;
}
Compilation message
bridges.cpp: In function 'int main()':
bridges.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d %d %d", &x, &y, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
bridges.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d %d %d", &qt[i], &qa[i], &qb[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
15 ms |
884 KB |
Output is correct |
4 |
Correct |
6 ms |
468 KB |
Output is correct |
5 |
Correct |
9 ms |
692 KB |
Output is correct |
6 |
Correct |
8 ms |
696 KB |
Output is correct |
7 |
Correct |
11 ms |
672 KB |
Output is correct |
8 |
Correct |
12 ms |
680 KB |
Output is correct |
9 |
Correct |
14 ms |
680 KB |
Output is correct |
10 |
Correct |
13 ms |
596 KB |
Output is correct |
11 |
Correct |
12 ms |
596 KB |
Output is correct |
12 |
Correct |
13 ms |
672 KB |
Output is correct |
13 |
Correct |
13 ms |
728 KB |
Output is correct |
14 |
Correct |
14 ms |
696 KB |
Output is correct |
15 |
Correct |
14 ms |
664 KB |
Output is correct |
16 |
Correct |
14 ms |
652 KB |
Output is correct |
17 |
Correct |
12 ms |
612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1300 ms |
4464 KB |
Output is correct |
2 |
Correct |
1278 ms |
7368 KB |
Output is correct |
3 |
Correct |
1261 ms |
7364 KB |
Output is correct |
4 |
Correct |
1252 ms |
7176 KB |
Output is correct |
5 |
Correct |
1228 ms |
7328 KB |
Output is correct |
6 |
Correct |
1400 ms |
8008 KB |
Output is correct |
7 |
Correct |
1406 ms |
8000 KB |
Output is correct |
8 |
Correct |
1363 ms |
8052 KB |
Output is correct |
9 |
Correct |
38 ms |
3348 KB |
Output is correct |
10 |
Correct |
892 ms |
7048 KB |
Output is correct |
11 |
Correct |
882 ms |
6820 KB |
Output is correct |
12 |
Correct |
1094 ms |
7992 KB |
Output is correct |
13 |
Correct |
1170 ms |
8252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
878 ms |
3780 KB |
Output is correct |
2 |
Correct |
371 ms |
4448 KB |
Output is correct |
3 |
Correct |
875 ms |
6232 KB |
Output is correct |
4 |
Correct |
873 ms |
6400 KB |
Output is correct |
5 |
Correct |
37 ms |
3352 KB |
Output is correct |
6 |
Correct |
879 ms |
6420 KB |
Output is correct |
7 |
Correct |
833 ms |
6168 KB |
Output is correct |
8 |
Correct |
802 ms |
6176 KB |
Output is correct |
9 |
Correct |
728 ms |
6352 KB |
Output is correct |
10 |
Correct |
701 ms |
5980 KB |
Output is correct |
11 |
Correct |
782 ms |
6864 KB |
Output is correct |
12 |
Correct |
755 ms |
6604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1555 ms |
5492 KB |
Output is correct |
2 |
Correct |
37 ms |
3276 KB |
Output is correct |
3 |
Correct |
166 ms |
4692 KB |
Output is correct |
4 |
Correct |
148 ms |
4672 KB |
Output is correct |
5 |
Correct |
1455 ms |
7604 KB |
Output is correct |
6 |
Correct |
1501 ms |
6972 KB |
Output is correct |
7 |
Correct |
1479 ms |
7676 KB |
Output is correct |
8 |
Correct |
740 ms |
5324 KB |
Output is correct |
9 |
Correct |
747 ms |
5260 KB |
Output is correct |
10 |
Correct |
748 ms |
6144 KB |
Output is correct |
11 |
Correct |
1176 ms |
6076 KB |
Output is correct |
12 |
Correct |
1122 ms |
6088 KB |
Output is correct |
13 |
Correct |
1186 ms |
7836 KB |
Output is correct |
14 |
Correct |
1478 ms |
8744 KB |
Output is correct |
15 |
Correct |
1478 ms |
7876 KB |
Output is correct |
16 |
Correct |
1608 ms |
6844 KB |
Output is correct |
17 |
Correct |
1624 ms |
6812 KB |
Output is correct |
18 |
Correct |
1584 ms |
6800 KB |
Output is correct |
19 |
Correct |
1565 ms |
6868 KB |
Output is correct |
20 |
Correct |
1390 ms |
8276 KB |
Output is correct |
21 |
Correct |
1425 ms |
8088 KB |
Output is correct |
22 |
Correct |
1550 ms |
8536 KB |
Output is correct |
23 |
Correct |
1250 ms |
7952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1300 ms |
4464 KB |
Output is correct |
2 |
Correct |
1278 ms |
7368 KB |
Output is correct |
3 |
Correct |
1261 ms |
7364 KB |
Output is correct |
4 |
Correct |
1252 ms |
7176 KB |
Output is correct |
5 |
Correct |
1228 ms |
7328 KB |
Output is correct |
6 |
Correct |
1400 ms |
8008 KB |
Output is correct |
7 |
Correct |
1406 ms |
8000 KB |
Output is correct |
8 |
Correct |
1363 ms |
8052 KB |
Output is correct |
9 |
Correct |
38 ms |
3348 KB |
Output is correct |
10 |
Correct |
892 ms |
7048 KB |
Output is correct |
11 |
Correct |
882 ms |
6820 KB |
Output is correct |
12 |
Correct |
1094 ms |
7992 KB |
Output is correct |
13 |
Correct |
1170 ms |
8252 KB |
Output is correct |
14 |
Correct |
878 ms |
3780 KB |
Output is correct |
15 |
Correct |
371 ms |
4448 KB |
Output is correct |
16 |
Correct |
875 ms |
6232 KB |
Output is correct |
17 |
Correct |
873 ms |
6400 KB |
Output is correct |
18 |
Correct |
37 ms |
3352 KB |
Output is correct |
19 |
Correct |
879 ms |
6420 KB |
Output is correct |
20 |
Correct |
833 ms |
6168 KB |
Output is correct |
21 |
Correct |
802 ms |
6176 KB |
Output is correct |
22 |
Correct |
728 ms |
6352 KB |
Output is correct |
23 |
Correct |
701 ms |
5980 KB |
Output is correct |
24 |
Correct |
782 ms |
6864 KB |
Output is correct |
25 |
Correct |
755 ms |
6604 KB |
Output is correct |
26 |
Correct |
1354 ms |
7328 KB |
Output is correct |
27 |
Correct |
1389 ms |
7168 KB |
Output is correct |
28 |
Correct |
1390 ms |
7208 KB |
Output is correct |
29 |
Correct |
1253 ms |
7476 KB |
Output is correct |
30 |
Correct |
1387 ms |
7372 KB |
Output is correct |
31 |
Correct |
1418 ms |
7332 KB |
Output is correct |
32 |
Correct |
1419 ms |
7196 KB |
Output is correct |
33 |
Correct |
1347 ms |
7296 KB |
Output is correct |
34 |
Correct |
1347 ms |
7332 KB |
Output is correct |
35 |
Correct |
1321 ms |
7352 KB |
Output is correct |
36 |
Correct |
1249 ms |
7392 KB |
Output is correct |
37 |
Correct |
1248 ms |
7272 KB |
Output is correct |
38 |
Correct |
1254 ms |
7704 KB |
Output is correct |
39 |
Correct |
1117 ms |
7196 KB |
Output is correct |
40 |
Correct |
1100 ms |
7280 KB |
Output is correct |
41 |
Correct |
1135 ms |
7068 KB |
Output is correct |
42 |
Correct |
1114 ms |
8284 KB |
Output is correct |
43 |
Correct |
1131 ms |
8068 KB |
Output is correct |
44 |
Correct |
1106 ms |
8276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
15 ms |
884 KB |
Output is correct |
4 |
Correct |
6 ms |
468 KB |
Output is correct |
5 |
Correct |
9 ms |
692 KB |
Output is correct |
6 |
Correct |
8 ms |
696 KB |
Output is correct |
7 |
Correct |
11 ms |
672 KB |
Output is correct |
8 |
Correct |
12 ms |
680 KB |
Output is correct |
9 |
Correct |
14 ms |
680 KB |
Output is correct |
10 |
Correct |
13 ms |
596 KB |
Output is correct |
11 |
Correct |
12 ms |
596 KB |
Output is correct |
12 |
Correct |
13 ms |
672 KB |
Output is correct |
13 |
Correct |
13 ms |
728 KB |
Output is correct |
14 |
Correct |
14 ms |
696 KB |
Output is correct |
15 |
Correct |
14 ms |
664 KB |
Output is correct |
16 |
Correct |
14 ms |
652 KB |
Output is correct |
17 |
Correct |
12 ms |
612 KB |
Output is correct |
18 |
Correct |
1300 ms |
4464 KB |
Output is correct |
19 |
Correct |
1278 ms |
7368 KB |
Output is correct |
20 |
Correct |
1261 ms |
7364 KB |
Output is correct |
21 |
Correct |
1252 ms |
7176 KB |
Output is correct |
22 |
Correct |
1228 ms |
7328 KB |
Output is correct |
23 |
Correct |
1400 ms |
8008 KB |
Output is correct |
24 |
Correct |
1406 ms |
8000 KB |
Output is correct |
25 |
Correct |
1363 ms |
8052 KB |
Output is correct |
26 |
Correct |
38 ms |
3348 KB |
Output is correct |
27 |
Correct |
892 ms |
7048 KB |
Output is correct |
28 |
Correct |
882 ms |
6820 KB |
Output is correct |
29 |
Correct |
1094 ms |
7992 KB |
Output is correct |
30 |
Correct |
1170 ms |
8252 KB |
Output is correct |
31 |
Correct |
878 ms |
3780 KB |
Output is correct |
32 |
Correct |
371 ms |
4448 KB |
Output is correct |
33 |
Correct |
875 ms |
6232 KB |
Output is correct |
34 |
Correct |
873 ms |
6400 KB |
Output is correct |
35 |
Correct |
37 ms |
3352 KB |
Output is correct |
36 |
Correct |
879 ms |
6420 KB |
Output is correct |
37 |
Correct |
833 ms |
6168 KB |
Output is correct |
38 |
Correct |
802 ms |
6176 KB |
Output is correct |
39 |
Correct |
728 ms |
6352 KB |
Output is correct |
40 |
Correct |
701 ms |
5980 KB |
Output is correct |
41 |
Correct |
782 ms |
6864 KB |
Output is correct |
42 |
Correct |
755 ms |
6604 KB |
Output is correct |
43 |
Correct |
1555 ms |
5492 KB |
Output is correct |
44 |
Correct |
37 ms |
3276 KB |
Output is correct |
45 |
Correct |
166 ms |
4692 KB |
Output is correct |
46 |
Correct |
148 ms |
4672 KB |
Output is correct |
47 |
Correct |
1455 ms |
7604 KB |
Output is correct |
48 |
Correct |
1501 ms |
6972 KB |
Output is correct |
49 |
Correct |
1479 ms |
7676 KB |
Output is correct |
50 |
Correct |
740 ms |
5324 KB |
Output is correct |
51 |
Correct |
747 ms |
5260 KB |
Output is correct |
52 |
Correct |
748 ms |
6144 KB |
Output is correct |
53 |
Correct |
1176 ms |
6076 KB |
Output is correct |
54 |
Correct |
1122 ms |
6088 KB |
Output is correct |
55 |
Correct |
1186 ms |
7836 KB |
Output is correct |
56 |
Correct |
1478 ms |
8744 KB |
Output is correct |
57 |
Correct |
1478 ms |
7876 KB |
Output is correct |
58 |
Correct |
1608 ms |
6844 KB |
Output is correct |
59 |
Correct |
1624 ms |
6812 KB |
Output is correct |
60 |
Correct |
1584 ms |
6800 KB |
Output is correct |
61 |
Correct |
1565 ms |
6868 KB |
Output is correct |
62 |
Correct |
1390 ms |
8276 KB |
Output is correct |
63 |
Correct |
1425 ms |
8088 KB |
Output is correct |
64 |
Correct |
1550 ms |
8536 KB |
Output is correct |
65 |
Correct |
1250 ms |
7952 KB |
Output is correct |
66 |
Correct |
1354 ms |
7328 KB |
Output is correct |
67 |
Correct |
1389 ms |
7168 KB |
Output is correct |
68 |
Correct |
1390 ms |
7208 KB |
Output is correct |
69 |
Correct |
1253 ms |
7476 KB |
Output is correct |
70 |
Correct |
1387 ms |
7372 KB |
Output is correct |
71 |
Correct |
1418 ms |
7332 KB |
Output is correct |
72 |
Correct |
1419 ms |
7196 KB |
Output is correct |
73 |
Correct |
1347 ms |
7296 KB |
Output is correct |
74 |
Correct |
1347 ms |
7332 KB |
Output is correct |
75 |
Correct |
1321 ms |
7352 KB |
Output is correct |
76 |
Correct |
1249 ms |
7392 KB |
Output is correct |
77 |
Correct |
1248 ms |
7272 KB |
Output is correct |
78 |
Correct |
1254 ms |
7704 KB |
Output is correct |
79 |
Correct |
1117 ms |
7196 KB |
Output is correct |
80 |
Correct |
1100 ms |
7280 KB |
Output is correct |
81 |
Correct |
1135 ms |
7068 KB |
Output is correct |
82 |
Correct |
1114 ms |
8284 KB |
Output is correct |
83 |
Correct |
1131 ms |
8068 KB |
Output is correct |
84 |
Correct |
1106 ms |
8276 KB |
Output is correct |
85 |
Correct |
2538 ms |
10184 KB |
Output is correct |
86 |
Correct |
250 ms |
5976 KB |
Output is correct |
87 |
Correct |
159 ms |
6212 KB |
Output is correct |
88 |
Correct |
1620 ms |
9132 KB |
Output is correct |
89 |
Correct |
2528 ms |
10124 KB |
Output is correct |
90 |
Correct |
1676 ms |
9012 KB |
Output is correct |
91 |
Correct |
1329 ms |
7252 KB |
Output is correct |
92 |
Correct |
1364 ms |
7304 KB |
Output is correct |
93 |
Correct |
1460 ms |
7888 KB |
Output is correct |
94 |
Correct |
1920 ms |
8536 KB |
Output is correct |
95 |
Correct |
1977 ms |
8652 KB |
Output is correct |
96 |
Correct |
1951 ms |
10100 KB |
Output is correct |
97 |
Correct |
1504 ms |
9212 KB |
Output is correct |
98 |
Correct |
1599 ms |
9288 KB |
Output is correct |
99 |
Correct |
2641 ms |
10004 KB |
Output is correct |
100 |
Correct |
2664 ms |
9980 KB |
Output is correct |
101 |
Correct |
2675 ms |
10140 KB |
Output is correct |
102 |
Correct |
2685 ms |
10072 KB |
Output is correct |
103 |
Correct |
2198 ms |
10740 KB |
Output is correct |
104 |
Correct |
2189 ms |
10408 KB |
Output is correct |
105 |
Correct |
2185 ms |
10652 KB |
Output is correct |
106 |
Correct |
1853 ms |
10260 KB |
Output is correct |
107 |
Correct |
1954 ms |
10424 KB |
Output is correct |
108 |
Correct |
2407 ms |
11120 KB |
Output is correct |
109 |
Correct |
1368 ms |
9324 KB |
Output is correct |