oj.uz

Submission #82509

# Submission time Handle Problem Language Result Execution time Memory
82509 2018-10-31T08:00:32 Z Good Evacuation plan (IZhO18_plan) C++11
19 / 100
 3339 ms 20788 KB 
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

#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 ans[N];
int Par[N];
int L[N], R[N];
int v[N], vis[N];
pii p[N * 5], P[N * 5];
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++)
		L[i] = 0, R[i] = 1e9, 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 p = Q.top();
		Q.pop();
		
		if(vis[p.ss] == 1) continue;
		vis[p.ss] = 1;
		
		for(auto i: E[p.ss])
			if (i.ss + p.ff < v[i.ff])
				v[i.ff] = i.ss + p.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;
	
	P[0] = {-1, -1};
	for(int j = 1; j <= 31; j++) {
		set <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.insert({(L[i] + R[i])/2, i});
		
		memset(vis, 0, sizeof (vis));
		
		for(int i = n; i >= 1; i--)
		{
			int nd = P[i].ss;
			
			vis[nd] = 1;
			for(auto h: E[nd])
				if (vis[h.ff] == 1) uni(nd, h.ff);
			
			if (!M.empty()) {
				pii last = *M.rbegin();
				
				while(!M.empty() && 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;
					
					M.erase(last);
					
					if(!M.empty()) last = *M.rbegin();
				}
			}
		}
	}
	
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3068 KB Output is correct
2 Correct 12 ms 3192 KB Output is correct
3 Correct 12 ms 3192 KB Output is correct
4 Incorrect 5 ms 3064 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3068 KB Output is correct
2 Correct 12 ms 3192 KB Output is correct
3 Correct 12 ms 3192 KB Output is correct
4 Incorrect 5 ms 3064 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1545 ms 12584 KB Output is correct
2 Correct 3245 ms 20592 KB Output is correct
3 Correct 3179 ms 20584 KB Output is correct
4 Correct 483 ms 9564 KB Output is correct
5 Correct 3198 ms 20548 KB Output is correct
6 Correct 3281 ms 20788 KB Output is correct
7 Correct 3286 ms 20592 KB Output is correct
8 Correct 3281 ms 20716 KB Output is correct
9 Correct 3310 ms 20592 KB Output is correct
10 Correct 3314 ms 20588 KB Output is correct
11 Correct 3266 ms 20584 KB Output is correct
12 Correct 3295 ms 20596 KB Output is correct
13 Correct 3190 ms 20576 KB Output is correct
14 Correct 3208 ms 20652 KB Output is correct
15 Correct 3237 ms 20676 KB Output is correct
16 Correct 3191 ms 20580 KB Output is correct
17 Correct 3177 ms 20588 KB Output is correct
18 Correct 3266 ms 20552 KB Output is correct
19 Correct 396 ms 9080 KB Output is correct
20 Correct 3339 ms 20580 KB Output is correct
21 Correct 2710 ms 20440 KB Output is correct
22 Correct 320 ms 10216 KB Output is correct
23 Correct 417 ms 9128 KB Output is correct
24 Correct 318 ms 10200 KB Output is correct
25 Correct 320 ms 10212 KB Output is correct
26 Correct 424 ms 9208 KB Output is correct
27 Correct 450 ms 9336 KB Output is correct
28 Correct 329 ms 10216 KB Output is correct
29 Correct 451 ms 9336 KB Output is correct
30 Correct 334 ms 10268 KB Output is correct
31 Correct 479 ms 9252 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3068 KB Output is correct
2 Correct 12 ms 3192 KB Output is correct
3 Correct 12 ms 3192 KB Output is correct
4 Incorrect 5 ms 3064 KB Output isn't correct
5 Halted 0 ms 0 KB -