# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
96904 | 2019-02-12T18:04:35 Z | Kalam | Evacuation plan (IZhO18_plan) | C++11 | 1095 ms | 67048 KB |
// KALAM # include<bits/stdc++.h> using namespace std; const int N = 500000 + 77; int n , m , q , k , d[N] , Ev[N] , Eu[N] , Ew[N] , Qv[N] , Qu[N] , P[N] , A[N] , Par[N]; bool M[N]; vector < int > a[N]; set < int > S[N]; priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Pq; bool CMP(int x , int y){ return Ew[x] > Ew[y]; } int Find(int x){ return Par[x] < 0 ? x : (Par[x] = Find(Par[x])); } inline void Merge(int v , int u , int w){ v = Find(v); u = Find(u); if(v == u) return ; if(Par[v] > Par[u]) swap(v , u); Par[v] += Par[u]; Par[u] = v; for(int x : S[u]){ auto it = S[v].lower_bound(x); if(it != S[v].end() && (*it) == x) A[x] = w , S[v].erase(it); else S[v].insert(x); } S[u].clear(); } int main(){ memset(Par , - 1 , sizeof(Par)); memset(d , 63 , sizeof(d)); scanf("%d %d" , & n , & m); for(int i = 1;i <= m;++ i) { scanf("%d %d %d" , Ev + i , Eu + i , Ew + i); a[Ev[i]].push_back(i); a[Eu[i]].push_back(i); } scanf("%d" , & k); while(k --){ int x; scanf("%d" , & x); d[x] = 0; Pq.push(make_pair(d[x] , x)); } while(! Pq.empty()){ int v = Pq.top().second; Pq.pop(); if(M[v]) continue ; M[v] = 1; for(int id : a[v]){ int u = Ev[id] ^ v ^ Eu[id] , w = Ew[id]; if(d[u] <= d[v] + w) continue ; d[u] = d[v] + w; Pq.push(make_pair(d[u] , u)); } } for(int i = 1;i <= m;++ i) P[i] = i , Ew[i] = min(d[Ev[i]] , d[Eu[i]]); sort(P + 1 , P + 1 + m , CMP); scanf("%d" , & q); for(int i = 1;i <= q;++ i){ scanf("%d %d" , Qv + i , Qu + i); S[Qv[i]].insert(i); S[Qu[i]].insert(i); } for(int i = 1;i <= m;++ i){ int id = P[i]; Merge(Ev[id] , Eu[id] , Ew[id]); } for(int i = 1;i <= q;++ i) printf("%d\n" , A[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 39544 KB | Output is correct |
2 | Correct | 39 ms | 39672 KB | Output is correct |
3 | Correct | 38 ms | 39648 KB | Output is correct |
4 | Correct | 44 ms | 39556 KB | Output is correct |
5 | Correct | 40 ms | 39644 KB | Output is correct |
6 | Correct | 46 ms | 39720 KB | Output is correct |
7 | Correct | 39 ms | 39572 KB | Output is correct |
8 | Correct | 37 ms | 39544 KB | Output is correct |
9 | Correct | 43 ms | 39800 KB | Output is correct |
10 | Correct | 39 ms | 39656 KB | Output is correct |
11 | Correct | 38 ms | 39672 KB | Output is correct |
12 | Correct | 38 ms | 39692 KB | Output is correct |
13 | Correct | 39 ms | 39676 KB | Output is correct |
14 | Correct | 38 ms | 39672 KB | Output is correct |
15 | Correct | 38 ms | 39672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 39544 KB | Output is correct |
2 | Correct | 39 ms | 39672 KB | Output is correct |
3 | Correct | 38 ms | 39648 KB | Output is correct |
4 | Correct | 44 ms | 39556 KB | Output is correct |
5 | Correct | 40 ms | 39644 KB | Output is correct |
6 | Correct | 46 ms | 39720 KB | Output is correct |
7 | Correct | 39 ms | 39572 KB | Output is correct |
8 | Correct | 37 ms | 39544 KB | Output is correct |
9 | Correct | 43 ms | 39800 KB | Output is correct |
10 | Correct | 39 ms | 39656 KB | Output is correct |
11 | Correct | 38 ms | 39672 KB | Output is correct |
12 | Correct | 38 ms | 39692 KB | Output is correct |
13 | Correct | 39 ms | 39676 KB | Output is correct |
14 | Correct | 38 ms | 39672 KB | Output is correct |
15 | Correct | 38 ms | 39672 KB | Output is correct |
16 | Correct | 348 ms | 55172 KB | Output is correct |
17 | Correct | 854 ms | 66872 KB | Output is correct |
18 | Correct | 86 ms | 42104 KB | Output is correct |
19 | Correct | 305 ms | 56576 KB | Output is correct |
20 | Correct | 952 ms | 66896 KB | Output is correct |
21 | Correct | 489 ms | 58464 KB | Output is correct |
22 | Correct | 250 ms | 55816 KB | Output is correct |
23 | Correct | 876 ms | 66856 KB | Output is correct |
24 | Correct | 894 ms | 66880 KB | Output is correct |
25 | Correct | 926 ms | 66780 KB | Output is correct |
26 | Correct | 302 ms | 56244 KB | Output is correct |
27 | Correct | 302 ms | 56420 KB | Output is correct |
28 | Correct | 290 ms | 56224 KB | Output is correct |
29 | Correct | 308 ms | 56468 KB | Output is correct |
30 | Correct | 300 ms | 56444 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 39544 KB | Output is correct |
2 | Correct | 37 ms | 39544 KB | Output is correct |
3 | Correct | 37 ms | 39496 KB | Output is correct |
4 | Correct | 37 ms | 39544 KB | Output is correct |
5 | Correct | 37 ms | 39544 KB | Output is correct |
6 | Correct | 39 ms | 39516 KB | Output is correct |
7 | Correct | 38 ms | 39448 KB | Output is correct |
8 | Correct | 37 ms | 39464 KB | Output is correct |
9 | Correct | 37 ms | 39544 KB | Output is correct |
10 | Correct | 36 ms | 39548 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 260 ms | 47724 KB | Output is correct |
2 | Correct | 592 ms | 56692 KB | Output is correct |
3 | Correct | 585 ms | 56768 KB | Output is correct |
4 | Correct | 137 ms | 44280 KB | Output is correct |
5 | Correct | 669 ms | 56768 KB | Output is correct |
6 | Correct | 567 ms | 56664 KB | Output is correct |
7 | Correct | 599 ms | 56696 KB | Output is correct |
8 | Correct | 599 ms | 56648 KB | Output is correct |
9 | Correct | 607 ms | 56684 KB | Output is correct |
10 | Correct | 589 ms | 56712 KB | Output is correct |
11 | Correct | 568 ms | 56724 KB | Output is correct |
12 | Correct | 594 ms | 56616 KB | Output is correct |
13 | Correct | 590 ms | 56652 KB | Output is correct |
14 | Correct | 567 ms | 56716 KB | Output is correct |
15 | Correct | 567 ms | 56732 KB | Output is correct |
16 | Correct | 576 ms | 56780 KB | Output is correct |
17 | Correct | 573 ms | 56708 KB | Output is correct |
18 | Correct | 565 ms | 56672 KB | Output is correct |
19 | Correct | 129 ms | 44384 KB | Output is correct |
20 | Correct | 571 ms | 56756 KB | Output is correct |
21 | Correct | 505 ms | 56428 KB | Output is correct |
22 | Correct | 131 ms | 45656 KB | Output is correct |
23 | Correct | 137 ms | 44408 KB | Output is correct |
24 | Correct | 138 ms | 45640 KB | Output is correct |
25 | Correct | 141 ms | 45548 KB | Output is correct |
26 | Correct | 151 ms | 44532 KB | Output is correct |
27 | Correct | 139 ms | 44284 KB | Output is correct |
28 | Correct | 139 ms | 45644 KB | Output is correct |
29 | Correct | 136 ms | 44280 KB | Output is correct |
30 | Correct | 131 ms | 45676 KB | Output is correct |
31 | Correct | 139 ms | 44336 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 37 ms | 39544 KB | Output is correct |
2 | Correct | 39 ms | 39672 KB | Output is correct |
3 | Correct | 38 ms | 39648 KB | Output is correct |
4 | Correct | 44 ms | 39556 KB | Output is correct |
5 | Correct | 40 ms | 39644 KB | Output is correct |
6 | Correct | 46 ms | 39720 KB | Output is correct |
7 | Correct | 39 ms | 39572 KB | Output is correct |
8 | Correct | 37 ms | 39544 KB | Output is correct |
9 | Correct | 43 ms | 39800 KB | Output is correct |
10 | Correct | 39 ms | 39656 KB | Output is correct |
11 | Correct | 38 ms | 39672 KB | Output is correct |
12 | Correct | 38 ms | 39692 KB | Output is correct |
13 | Correct | 39 ms | 39676 KB | Output is correct |
14 | Correct | 38 ms | 39672 KB | Output is correct |
15 | Correct | 38 ms | 39672 KB | Output is correct |
16 | Correct | 348 ms | 55172 KB | Output is correct |
17 | Correct | 854 ms | 66872 KB | Output is correct |
18 | Correct | 86 ms | 42104 KB | Output is correct |
19 | Correct | 305 ms | 56576 KB | Output is correct |
20 | Correct | 952 ms | 66896 KB | Output is correct |
21 | Correct | 489 ms | 58464 KB | Output is correct |
22 | Correct | 250 ms | 55816 KB | Output is correct |
23 | Correct | 876 ms | 66856 KB | Output is correct |
24 | Correct | 894 ms | 66880 KB | Output is correct |
25 | Correct | 926 ms | 66780 KB | Output is correct |
26 | Correct | 302 ms | 56244 KB | Output is correct |
27 | Correct | 302 ms | 56420 KB | Output is correct |
28 | Correct | 290 ms | 56224 KB | Output is correct |
29 | Correct | 308 ms | 56468 KB | Output is correct |
30 | Correct | 300 ms | 56444 KB | Output is correct |
31 | Correct | 37 ms | 39544 KB | Output is correct |
32 | Correct | 37 ms | 39544 KB | Output is correct |
33 | Correct | 37 ms | 39496 KB | Output is correct |
34 | Correct | 37 ms | 39544 KB | Output is correct |
35 | Correct | 37 ms | 39544 KB | Output is correct |
36 | Correct | 39 ms | 39516 KB | Output is correct |
37 | Correct | 38 ms | 39448 KB | Output is correct |
38 | Correct | 37 ms | 39464 KB | Output is correct |
39 | Correct | 37 ms | 39544 KB | Output is correct |
40 | Correct | 36 ms | 39548 KB | Output is correct |
41 | Correct | 260 ms | 47724 KB | Output is correct |
42 | Correct | 592 ms | 56692 KB | Output is correct |
43 | Correct | 585 ms | 56768 KB | Output is correct |
44 | Correct | 137 ms | 44280 KB | Output is correct |
45 | Correct | 669 ms | 56768 KB | Output is correct |
46 | Correct | 567 ms | 56664 KB | Output is correct |
47 | Correct | 599 ms | 56696 KB | Output is correct |
48 | Correct | 599 ms | 56648 KB | Output is correct |
49 | Correct | 607 ms | 56684 KB | Output is correct |
50 | Correct | 589 ms | 56712 KB | Output is correct |
51 | Correct | 568 ms | 56724 KB | Output is correct |
52 | Correct | 594 ms | 56616 KB | Output is correct |
53 | Correct | 590 ms | 56652 KB | Output is correct |
54 | Correct | 567 ms | 56716 KB | Output is correct |
55 | Correct | 567 ms | 56732 KB | Output is correct |
56 | Correct | 576 ms | 56780 KB | Output is correct |
57 | Correct | 573 ms | 56708 KB | Output is correct |
58 | Correct | 565 ms | 56672 KB | Output is correct |
59 | Correct | 129 ms | 44384 KB | Output is correct |
60 | Correct | 571 ms | 56756 KB | Output is correct |
61 | Correct | 505 ms | 56428 KB | Output is correct |
62 | Correct | 131 ms | 45656 KB | Output is correct |
63 | Correct | 137 ms | 44408 KB | Output is correct |
64 | Correct | 138 ms | 45640 KB | Output is correct |
65 | Correct | 141 ms | 45548 KB | Output is correct |
66 | Correct | 151 ms | 44532 KB | Output is correct |
67 | Correct | 139 ms | 44284 KB | Output is correct |
68 | Correct | 139 ms | 45644 KB | Output is correct |
69 | Correct | 136 ms | 44280 KB | Output is correct |
70 | Correct | 131 ms | 45676 KB | Output is correct |
71 | Correct | 139 ms | 44336 KB | Output is correct |
72 | Correct | 526 ms | 58828 KB | Output is correct |
73 | Correct | 876 ms | 66924 KB | Output is correct |
74 | Correct | 888 ms | 66896 KB | Output is correct |
75 | Correct | 917 ms | 66948 KB | Output is correct |
76 | Correct | 956 ms | 66976 KB | Output is correct |
77 | Correct | 910 ms | 66936 KB | Output is correct |
78 | Correct | 878 ms | 67020 KB | Output is correct |
79 | Correct | 901 ms | 67024 KB | Output is correct |
80 | Correct | 933 ms | 66932 KB | Output is correct |
81 | Correct | 941 ms | 66892 KB | Output is correct |
82 | Correct | 913 ms | 66940 KB | Output is correct |
83 | Correct | 858 ms | 66956 KB | Output is correct |
84 | Correct | 972 ms | 66960 KB | Output is correct |
85 | Correct | 856 ms | 67048 KB | Output is correct |
86 | Correct | 817 ms | 66968 KB | Output is correct |
87 | Correct | 863 ms | 66880 KB | Output is correct |
88 | Correct | 1095 ms | 66924 KB | Output is correct |
89 | Correct | 379 ms | 55808 KB | Output is correct |
90 | Correct | 850 ms | 66936 KB | Output is correct |
91 | Correct | 841 ms | 66480 KB | Output is correct |
92 | Correct | 382 ms | 56392 KB | Output is correct |
93 | Correct | 545 ms | 56004 KB | Output is correct |
94 | Correct | 392 ms | 56236 KB | Output is correct |
95 | Correct | 385 ms | 56368 KB | Output is correct |
96 | Correct | 597 ms | 55360 KB | Output is correct |
97 | Correct | 437 ms | 55432 KB | Output is correct |
98 | Correct | 364 ms | 56284 KB | Output is correct |
99 | Correct | 402 ms | 55428 KB | Output is correct |
100 | Correct | 379 ms | 56356 KB | Output is correct |