#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize9("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MS = (int)1e5 + 4;
int n, m, q;
vector<int> way[MS];
int l[MS], r[MS];
int rst[504], rstN, lev[MS], rev[MS];
int lst[504], lstN;
int pr[504];
inline int fd(int x){
return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}
inline bool unite(int x, int y){
x = fd(x), y = fd(y);
if(x == y) return false;
pr[y] = x;
return true;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
memset(lev, -1, sizeof(lev)), memset(rev, -1, sizeof(rev));
cin >> n >> m;
//n = 500, m = 499;
for(int i = 0; i < m; ++i){
way[i].resize(3);
cin >> way[i][1] >> way[i][2] >> way[i][0];
//way[i][1] = i + 1, way[i][2] = i + 2, way[i][0] = i + 30;
l[i] = -1, r[i] = m;
}
cin >> q; //q = 1000000;
sort(way, way + m);
for(int i = 0; i < m; ++i){
for(int i = 1; i <= n; ++i){
pr[i] = i;
}
unite(way[i][1], way[i][2]);
int pos = lstN;
while(pos){
if(!unite(way[lst[pos]][1], way[lst[pos]][2])){
break;
}
--pos;
}
if(pos){
lev[i] = lst[pos];
l[i] = lev[i] + 1;
for(int k = pos; k < lstN; ++k){
lst[k] = lst[k + 1];
}
lst[lstN] = i;
}
else{
l[i] = -1;
lst[++lstN] = i;
}
}
lstN = 0;
for(int i = m - 1; i >= 0; --i){
if(rstN >= n - 1){
r[i] = rst[1] - 1;
}
for(int i = 1; i <= n; ++i){
pr[i] = i;
}
unite(way[i][1], way[i][2]);
int pos = rstN;
while(pos){
if(!unite(way[rst[pos]][1], way[rst[pos]][2])){
break;
}
--pos;
}
if(pos){
rev[i] = rst[pos];
r[i] = rev[i] - 1;
for(int k = pos; k < rstN; ++k){
rst[k] = rst[k + 1];
}
rst[rstN] = i;
}
else{
r[i] = m;
rst[++rstN] = i;
}
}
int rp = 0;
while(q--){
int x; cin >> x;
//x = q + 100;
while(rp < m && way[rp][0] < x){
if(rev[rp] == -1){
--rstN;
}
else{
for(int i = rstN; ; --i){
if(i > 1 && rst[i - 1] < rev[rp]){
rst[i] = rst[i - 1];
}
else{
rst[i] = rev[rp];
break;
}
}
}
if(lev[rp] == -1){
lst[++lstN] = rp;
}
else{
int pos = lower_bound(lst + 1, lst + lstN + 1, lev[rp]) - lst;
for(int i = pos; i < lstN; ++i){
lst[i] = lst[i + 1];
}
lst[lstN] = rp;
}
++rp;
}
int lid = lstN, rid = rstN, cnt = 0;
assert(lid <= 500 && rid <= 500);
lst[lid + 1] = (int)2e9, rst[rid + 1] = -100;
long long ans = 0;
T:
if(lid > 0 && r[lst[lid]] < rst[rid + 1]){
--lid; goto T;
}
T2:
if(rid > 0 && l[rst[rid]] > lst[lid + 1]){
--rid; goto T2;
}
if(!rid || (lid && x - way[lst[lid]][0] < way[rst[rid]][0] - x)){
ans += x - way[lst[lid]][0];
--lid;
}
else{
ans += way[rst[rid]][0] - x;
--rid;
}
++cnt;
if(cnt < n - 1) goto T;
cout << ans << '\n';
}
return 0;
}
Compilation message
reconstruction.cpp:3: warning: ignoring '#pragma GCC optimize9' [-Wunknown-pragmas]
3 | #pragma GCC optimize9("Ofast")
|
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
3 ms |
3412 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
3 ms |
3412 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
1665 ms |
7448 KB |
Output is correct |
21 |
Correct |
803 ms |
7412 KB |
Output is correct |
22 |
Correct |
839 ms |
7348 KB |
Output is correct |
23 |
Correct |
934 ms |
7352 KB |
Output is correct |
24 |
Correct |
1219 ms |
7348 KB |
Output is correct |
25 |
Correct |
1591 ms |
7352 KB |
Output is correct |
26 |
Correct |
1708 ms |
7372 KB |
Output is correct |
27 |
Correct |
1702 ms |
7432 KB |
Output is correct |
28 |
Correct |
1661 ms |
7348 KB |
Output is correct |
29 |
Correct |
636 ms |
7352 KB |
Output is correct |
30 |
Correct |
1689 ms |
7352 KB |
Output is correct |
31 |
Correct |
1694 ms |
7348 KB |
Output is correct |
32 |
Correct |
1706 ms |
7352 KB |
Output is correct |
33 |
Correct |
1646 ms |
7348 KB |
Output is correct |
34 |
Correct |
774 ms |
7376 KB |
Output is correct |
35 |
Correct |
1659 ms |
7352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
3 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Execution timed out |
5095 ms |
13368 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
3 ms |
3412 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
3332 ms |
15668 KB |
Output is correct |
21 |
Correct |
3162 ms |
15892 KB |
Output is correct |
22 |
Correct |
3338 ms |
15792 KB |
Output is correct |
23 |
Correct |
3243 ms |
15724 KB |
Output is correct |
24 |
Correct |
3322 ms |
15748 KB |
Output is correct |
25 |
Correct |
3331 ms |
15724 KB |
Output is correct |
26 |
Correct |
3232 ms |
15648 KB |
Output is correct |
27 |
Correct |
2581 ms |
15828 KB |
Output is correct |
28 |
Correct |
3328 ms |
15664 KB |
Output is correct |
29 |
Correct |
3304 ms |
15724 KB |
Output is correct |
30 |
Correct |
3305 ms |
15788 KB |
Output is correct |
31 |
Correct |
3357 ms |
15784 KB |
Output is correct |
32 |
Correct |
2664 ms |
16356 KB |
Output is correct |
33 |
Correct |
3518 ms |
15472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
3 ms |
3412 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
1665 ms |
7448 KB |
Output is correct |
21 |
Correct |
803 ms |
7412 KB |
Output is correct |
22 |
Correct |
839 ms |
7348 KB |
Output is correct |
23 |
Correct |
934 ms |
7352 KB |
Output is correct |
24 |
Correct |
1219 ms |
7348 KB |
Output is correct |
25 |
Correct |
1591 ms |
7352 KB |
Output is correct |
26 |
Correct |
1708 ms |
7372 KB |
Output is correct |
27 |
Correct |
1702 ms |
7432 KB |
Output is correct |
28 |
Correct |
1661 ms |
7348 KB |
Output is correct |
29 |
Correct |
636 ms |
7352 KB |
Output is correct |
30 |
Correct |
1689 ms |
7352 KB |
Output is correct |
31 |
Correct |
1694 ms |
7348 KB |
Output is correct |
32 |
Correct |
1706 ms |
7352 KB |
Output is correct |
33 |
Correct |
1646 ms |
7348 KB |
Output is correct |
34 |
Correct |
774 ms |
7376 KB |
Output is correct |
35 |
Correct |
1659 ms |
7352 KB |
Output is correct |
36 |
Correct |
1884 ms |
7460 KB |
Output is correct |
37 |
Correct |
959 ms |
7512 KB |
Output is correct |
38 |
Correct |
962 ms |
7476 KB |
Output is correct |
39 |
Correct |
1137 ms |
7564 KB |
Output is correct |
40 |
Correct |
1433 ms |
7516 KB |
Output is correct |
41 |
Correct |
1777 ms |
7480 KB |
Output is correct |
42 |
Correct |
1871 ms |
7480 KB |
Output is correct |
43 |
Correct |
1884 ms |
7476 KB |
Output is correct |
44 |
Correct |
1767 ms |
7476 KB |
Output is correct |
45 |
Correct |
687 ms |
7480 KB |
Output is correct |
46 |
Correct |
1830 ms |
7476 KB |
Output is correct |
47 |
Correct |
1877 ms |
7476 KB |
Output is correct |
48 |
Correct |
1874 ms |
7480 KB |
Output is correct |
49 |
Correct |
1880 ms |
7476 KB |
Output is correct |
50 |
Correct |
846 ms |
7600 KB |
Output is correct |
51 |
Correct |
1765 ms |
7476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3412 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
3 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Correct |
2 ms |
3412 KB |
Output is correct |
10 |
Correct |
2 ms |
3412 KB |
Output is correct |
11 |
Correct |
2 ms |
3412 KB |
Output is correct |
12 |
Correct |
2 ms |
3412 KB |
Output is correct |
13 |
Correct |
2 ms |
3412 KB |
Output is correct |
14 |
Correct |
2 ms |
3412 KB |
Output is correct |
15 |
Correct |
3 ms |
3412 KB |
Output is correct |
16 |
Correct |
2 ms |
3412 KB |
Output is correct |
17 |
Correct |
2 ms |
3412 KB |
Output is correct |
18 |
Correct |
2 ms |
3412 KB |
Output is correct |
19 |
Correct |
2 ms |
3412 KB |
Output is correct |
20 |
Correct |
1665 ms |
7448 KB |
Output is correct |
21 |
Correct |
803 ms |
7412 KB |
Output is correct |
22 |
Correct |
839 ms |
7348 KB |
Output is correct |
23 |
Correct |
934 ms |
7352 KB |
Output is correct |
24 |
Correct |
1219 ms |
7348 KB |
Output is correct |
25 |
Correct |
1591 ms |
7352 KB |
Output is correct |
26 |
Correct |
1708 ms |
7372 KB |
Output is correct |
27 |
Correct |
1702 ms |
7432 KB |
Output is correct |
28 |
Correct |
1661 ms |
7348 KB |
Output is correct |
29 |
Correct |
636 ms |
7352 KB |
Output is correct |
30 |
Correct |
1689 ms |
7352 KB |
Output is correct |
31 |
Correct |
1694 ms |
7348 KB |
Output is correct |
32 |
Correct |
1706 ms |
7352 KB |
Output is correct |
33 |
Correct |
1646 ms |
7348 KB |
Output is correct |
34 |
Correct |
774 ms |
7376 KB |
Output is correct |
35 |
Correct |
1659 ms |
7352 KB |
Output is correct |
36 |
Correct |
2 ms |
3412 KB |
Output is correct |
37 |
Correct |
3 ms |
3412 KB |
Output is correct |
38 |
Correct |
3 ms |
3412 KB |
Output is correct |
39 |
Execution timed out |
5095 ms |
13368 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |