oj.uz

Submission #82510

# Submission time Handle Problem Language Result Execution time Memory
82510 2018-10-31T08:04:51 Z Good Evacuation plan (IZhO18_plan) C++11
19 / 100
 3411 ms 20792 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};
	while (1) {
		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});
		
		if (!M.size())
			break;
		
		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 3064 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 3064 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 1484 ms 12504 KB Output is correct
2 Correct 3101 ms 20584 KB Output is correct
3 Correct 3137 ms 20792 KB Output is correct
4 Correct 615 ms 9452 KB Output is correct
5 Correct 3192 ms 20680 KB Output is correct
6 Correct 3142 ms 20644 KB Output is correct
7 Correct 3140 ms 20712 KB Output is correct
8 Correct 3155 ms 20700 KB Output is correct
9 Correct 3160 ms 20672 KB Output is correct
10 Correct 3411 ms 20692 KB Output is correct
11 Correct 3136 ms 20716 KB Output is correct
12 Correct 3121 ms 20760 KB Output is correct
13 Correct 3162 ms 20724 KB Output is correct
14 Correct 3158 ms 20728 KB Output is correct
15 Correct 3125 ms 20724 KB Output is correct
16 Correct 3128 ms 20536 KB Output is correct
17 Correct 3128 ms 20532 KB Output is correct
18 Correct 3106 ms 20588 KB Output is correct
19 Correct 348 ms 9200 KB Output is correct
20 Correct 3198 ms 20588 KB Output is correct
21 Correct 2674 ms 20244 KB Output is correct
22 Correct 325 ms 10216 KB Output is correct
23 Correct 371 ms 9060 KB Output is correct
24 Correct 320 ms 10208 KB Output is correct
25 Correct 327 ms 10220 KB Output is correct
26 Correct 441 ms 9308 KB Output is correct
27 Correct 513 ms 9376 KB Output is correct
28 Correct 320 ms 10284 KB Output is correct
29 Correct 481 ms 9440 KB Output is correct
30 Correct 329 ms 10300 KB Output is correct
31 Correct 539 ms 9388 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 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 -