답안 #82604 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82604	2018-10-31T18:41:30 Z	Good	Evacuation plan (IZhO18_plan)	C++11	100 / 100	3682 ms	24296 KB

plan

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

#define all(x) x.begin(), x.end()
#define N 100010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define pii pair <int, int>

using namespace std;

int k;
int n, m, q;
int a, b, c;

int v[N];
int ans[N];
int Par[N];
bool vis[N];
int L[N], R[N];
pii p[N], P[N];
vector <pii> E[N];
priority_queue <pii, vector <pii>, greater <pii>> Q;

int ata(int x)
{
	if (x == Par[x]) return x;
	
	return Par[x] = ata(Par[x]);
}

void uni(int x, int y) {
	x = ata(x);
	y = ata(y);
	
	if (x == y) return;
	
	Par[y] = x;
}

int main()
{
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		v[i] = 1e9;
	
	for(int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		
		E[a].pb({b, c});
		E[b].pb({a, c});
	}
	
	cin >> k;
	
	for(int i = 1; i <= k; i++) {
		cin >> a;
		Q.push({0, a}), v[a] = 0;
	}
	
	while(!Q.empty()) {
		pii t = Q.top();
		Q.pop();
		
		if(vis[t.ss]) continue;
		vis[t.ss] = 1;
		
		for(auto i: E[t.ss])
			if (i.ss + t.ff < v[i.ff])
				v[i.ff] = i.ss + t.ff, Q.push({v[i.ff], i.ff});
	}
	
	for(int i = 1; i <= n; i++) P[i] = {v[i], i};
	
	sort(P+1, P+n+1);
	
	cin >> q;
	
	for(int i = 1; i <= q; i++)
		cin >> p[i].ff >> p[i].ss, L[i] = 0, R[i] = 1e9;
	
	P[0] = {-1, -1};
	while (1) {
		vector <pii> M;
		
		for(int i = 1; i <= n; i++) Par[i] = i;
		
		for(int i = 1; i <= q; i++)
			if (L[i] <= R[i])
				M.pb({(L[i] + R[i])/2, i});
		
		if (!M.size())
			break;
		
		sort (all(M));
		memset(vis, 0, sizeof (vis));
		
		int pos = M.size() - 1;
		for(int i = n; i >= 1; i--)
		{
			int nd = P[i].ss;
			
			vis[nd] = 1;
			for(auto h: E[nd])
				if (vis[h.ff]) 
					uni(nd, h.ff);
			
			if (pos < 0)
				continue;
					
			pii last = M[pos];	
			while(last.ff > P[i-1].ff) {
				a = p[last.ss].ff;
				b = p[last.ss].ss;
				
				if (ata(a) == ata(b)) ans[last.ss] = last.ff, L[last.ss] = last.ff + 1;
				else R[last.ss] = last.ff - 1;
				
				pos --;
				if (pos < 0)
					break;
					
				last = M[pos];						
			}
		}
	}
	
	for(int i = 1; i <= q; i++) 
		cout << ans[i] << '\n';
}
/*
10 13
1 10 20
4 9 14
5 6 10
9 7 10
7 8 8
7 6 7
4 5 5
10 9 5
10 3 3
3 4 3
10 7 3
2 3 2
1 2 1
2
9 8
2
3 6
4 7
*/

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	8 ms	2936 KB	Output is correct
3	Correct	8 ms	2936 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	8 ms	2936 KB	Output is correct
6	Correct	9 ms	2940 KB	Output is correct
7	Correct	4 ms	2808 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	9 ms	2808 KB	Output is correct
10	Correct	10 ms	2936 KB	Output is correct
11	Correct	9 ms	2936 KB	Output is correct
12	Correct	8 ms	2936 KB	Output is correct
13	Correct	10 ms	2808 KB	Output is correct
14	Correct	10 ms	2808 KB	Output is correct
15	Correct	10 ms	2936 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	8 ms	2936 KB	Output is correct
3	Correct	8 ms	2936 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	8 ms	2936 KB	Output is correct
6	Correct	9 ms	2940 KB	Output is correct
7	Correct	4 ms	2808 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	9 ms	2808 KB	Output is correct
10	Correct	10 ms	2936 KB	Output is correct
11	Correct	9 ms	2936 KB	Output is correct
12	Correct	8 ms	2936 KB	Output is correct
13	Correct	10 ms	2808 KB	Output is correct
14	Correct	10 ms	2808 KB	Output is correct
15	Correct	10 ms	2936 KB	Output is correct
16	Correct	1044 ms	11640 KB	Output is correct
17	Correct	3530 ms	23316 KB	Output is correct
18	Correct	194 ms	5048 KB	Output is correct
19	Correct	618 ms	13072 KB	Output is correct
20	Correct	3511 ms	24296 KB	Output is correct
21	Correct	1624 ms	15668 KB	Output is correct
22	Correct	1096 ms	12016 KB	Output is correct
23	Correct	3517 ms	24164 KB	Output is correct
24	Correct	3541 ms	24136 KB	Output is correct
25	Correct	3501 ms	24128 KB	Output is correct
26	Correct	626 ms	13240 KB	Output is correct
27	Correct	634 ms	13144 KB	Output is correct
28	Correct	626 ms	13116 KB	Output is correct
29	Correct	623 ms	13160 KB	Output is correct
30	Correct	596 ms	13084 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	5 ms	2808 KB	Output is correct
3	Correct	4 ms	2808 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	4 ms	2808 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	4 ms	2808 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	4 ms	2808 KB	Output is correct
10	Correct	4 ms	2808 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1518 ms	11376 KB	Output is correct
2	Correct	3102 ms	19468 KB	Output is correct
3	Correct	3120 ms	19540 KB	Output is correct
4	Correct	509 ms	8300 KB	Output is correct
5	Correct	3135 ms	19424 KB	Output is correct
6	Correct	3115 ms	19652 KB	Output is correct
7	Correct	3129 ms	19544 KB	Output is correct
8	Correct	3092 ms	19488 KB	Output is correct
9	Correct	3096 ms	19412 KB	Output is correct
10	Correct	3145 ms	19600 KB	Output is correct
11	Correct	3092 ms	19472 KB	Output is correct
12	Correct	3099 ms	19536 KB	Output is correct
13	Correct	3148 ms	19648 KB	Output is correct
14	Correct	3163 ms	19656 KB	Output is correct
15	Correct	3189 ms	19492 KB	Output is correct
16	Correct	3144 ms	19648 KB	Output is correct
17	Correct	3094 ms	19516 KB	Output is correct
18	Correct	3142 ms	19664 KB	Output is correct
19	Correct	327 ms	7932 KB	Output is correct
20	Correct	3128 ms	19496 KB	Output is correct
21	Correct	2586 ms	19340 KB	Output is correct
22	Correct	303 ms	9196 KB	Output is correct
23	Correct	359 ms	8040 KB	Output is correct
24	Correct	307 ms	9188 KB	Output is correct
25	Correct	298 ms	9224 KB	Output is correct
26	Correct	402 ms	8144 KB	Output is correct
27	Correct	483 ms	8288 KB	Output is correct
28	Correct	300 ms	9192 KB	Output is correct
29	Correct	457 ms	8416 KB	Output is correct
30	Correct	299 ms	9236 KB	Output is correct
31	Correct	399 ms	8400 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2808 KB	Output is correct
2	Correct	8 ms	2936 KB	Output is correct
3	Correct	8 ms	2936 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	8 ms	2936 KB	Output is correct
6	Correct	9 ms	2940 KB	Output is correct
7	Correct	4 ms	2808 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	9 ms	2808 KB	Output is correct
10	Correct	10 ms	2936 KB	Output is correct
11	Correct	9 ms	2936 KB	Output is correct
12	Correct	8 ms	2936 KB	Output is correct
13	Correct	10 ms	2808 KB	Output is correct
14	Correct	10 ms	2808 KB	Output is correct
15	Correct	10 ms	2936 KB	Output is correct
16	Correct	1044 ms	11640 KB	Output is correct
17	Correct	3530 ms	23316 KB	Output is correct
18	Correct	194 ms	5048 KB	Output is correct
19	Correct	618 ms	13072 KB	Output is correct
20	Correct	3511 ms	24296 KB	Output is correct
21	Correct	1624 ms	15668 KB	Output is correct
22	Correct	1096 ms	12016 KB	Output is correct
23	Correct	3517 ms	24164 KB	Output is correct
24	Correct	3541 ms	24136 KB	Output is correct
25	Correct	3501 ms	24128 KB	Output is correct
26	Correct	626 ms	13240 KB	Output is correct
27	Correct	634 ms	13144 KB	Output is correct
28	Correct	626 ms	13116 KB	Output is correct
29	Correct	623 ms	13160 KB	Output is correct
30	Correct	596 ms	13084 KB	Output is correct
31	Correct	4 ms	2808 KB	Output is correct
32	Correct	5 ms	2808 KB	Output is correct
33	Correct	4 ms	2808 KB	Output is correct
34	Correct	4 ms	2808 KB	Output is correct
35	Correct	4 ms	2808 KB	Output is correct
36	Correct	4 ms	2808 KB	Output is correct
37	Correct	4 ms	2808 KB	Output is correct
38	Correct	4 ms	2808 KB	Output is correct
39	Correct	4 ms	2808 KB	Output is correct
40	Correct	4 ms	2808 KB	Output is correct
41	Correct	1518 ms	11376 KB	Output is correct
42	Correct	3102 ms	19468 KB	Output is correct
43	Correct	3120 ms	19540 KB	Output is correct
44	Correct	509 ms	8300 KB	Output is correct
45	Correct	3135 ms	19424 KB	Output is correct
46	Correct	3115 ms	19652 KB	Output is correct
47	Correct	3129 ms	19544 KB	Output is correct
48	Correct	3092 ms	19488 KB	Output is correct
49	Correct	3096 ms	19412 KB	Output is correct
50	Correct	3145 ms	19600 KB	Output is correct
51	Correct	3092 ms	19472 KB	Output is correct
52	Correct	3099 ms	19536 KB	Output is correct
53	Correct	3148 ms	19648 KB	Output is correct
54	Correct	3163 ms	19656 KB	Output is correct
55	Correct	3189 ms	19492 KB	Output is correct
56	Correct	3144 ms	19648 KB	Output is correct
57	Correct	3094 ms	19516 KB	Output is correct
58	Correct	3142 ms	19664 KB	Output is correct
59	Correct	327 ms	7932 KB	Output is correct
60	Correct	3128 ms	19496 KB	Output is correct
61	Correct	2586 ms	19340 KB	Output is correct
62	Correct	303 ms	9196 KB	Output is correct
63	Correct	359 ms	8040 KB	Output is correct
64	Correct	307 ms	9188 KB	Output is correct
65	Correct	298 ms	9224 KB	Output is correct
66	Correct	402 ms	8144 KB	Output is correct
67	Correct	483 ms	8288 KB	Output is correct
68	Correct	300 ms	9192 KB	Output is correct
69	Correct	457 ms	8416 KB	Output is correct
70	Correct	299 ms	9236 KB	Output is correct
71	Correct	399 ms	8400 KB	Output is correct
72	Correct	1879 ms	15172 KB	Output is correct
73	Correct	3528 ms	23284 KB	Output is correct
74	Correct	3527 ms	23260 KB	Output is correct
75	Correct	3522 ms	23200 KB	Output is correct
76	Correct	3556 ms	23264 KB	Output is correct
77	Correct	3525 ms	23300 KB	Output is correct
78	Correct	3557 ms	23284 KB	Output is correct
79	Correct	3530 ms	23220 KB	Output is correct
80	Correct	3559 ms	23380 KB	Output is correct
81	Correct	3592 ms	23416 KB	Output is correct
82	Correct	3665 ms	23276 KB	Output is correct
83	Correct	3591 ms	23216 KB	Output is correct
84	Correct	3500 ms	23300 KB	Output is correct
85	Correct	3600 ms	23432 KB	Output is correct
86	Correct	3682 ms	23276 KB	Output is correct
87	Correct	3636 ms	23216 KB	Output is correct
88	Correct	3572 ms	23304 KB	Output is correct
89	Correct	1377 ms	11932 KB	Output is correct
90	Correct	3556 ms	23268 KB	Output is correct
91	Correct	2950 ms	23016 KB	Output is correct
92	Correct	589 ms	12868 KB	Output is correct
93	Correct	1080 ms	12100 KB	Output is correct
94	Correct	594 ms	12952 KB	Output is correct
95	Correct	599 ms	12852 KB	Output is correct
96	Correct	983 ms	11932 KB	Output is correct
97	Correct	1308 ms	11872 KB	Output is correct
98	Correct	620 ms	12912 KB	Output is correct
99	Correct	1269 ms	11784 KB	Output is correct
100	Correct	595 ms	12848 KB	Output is correct

답안 #82604

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 13.0 / 13.0

Subtask #3 12.0 / 12.0

Subtask #4 19.0 / 19.0

Subtask #5 46.0 / 46.0

Subtask #1
10.0 / 10.0

Subtask #2
13.0 / 13.0

Subtask #3
12.0 / 12.0

Subtask #4
19.0 / 19.0

Subtask #5
46.0 / 46.0