oj.uz

Submission #82523

# Submission time Handle Problem Language Result Execution time Memory
82523 2018-10-31T09:30:15 Z Good Evacuation plan (IZhO18_plan) C++11
19 / 100
 3186 ms 20748 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 t = Q.top();
		Q.pop();
		
		if(vis[t.ss] == 1) 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;
	
	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 3240 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 3240 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 1540 ms 12512 KB Output is correct
2 Correct 3132 ms 20596 KB Output is correct
3 Correct 3052 ms 20520 KB Output is correct
4 Correct 491 ms 9408 KB Output is correct
5 Correct 3073 ms 20544 KB Output is correct
6 Correct 3149 ms 20588 KB Output is correct
7 Correct 3155 ms 20532 KB Output is correct
8 Correct 3136 ms 20548 KB Output is correct
9 Correct 3159 ms 20484 KB Output is correct
10 Correct 3138 ms 20744 KB Output is correct
11 Correct 3119 ms 20628 KB Output is correct
12 Correct 3142 ms 20716 KB Output is correct
13 Correct 3186 ms 20600 KB Output is correct
14 Correct 3146 ms 20712 KB Output is correct
15 Correct 3142 ms 20588 KB Output is correct
16 Correct 3116 ms 20644 KB Output is correct
17 Correct 3113 ms 20584 KB Output is correct
18 Correct 3134 ms 20612 KB Output is correct
19 Correct 336 ms 9080 KB Output is correct
20 Correct 3093 ms 20748 KB Output is correct
21 Correct 2662 ms 20408 KB Output is correct
22 Correct 335 ms 10344 KB Output is correct
23 Correct 369 ms 9076 KB Output is correct
24 Correct 329 ms 10348 KB Output is correct
25 Correct 325 ms 10396 KB Output is correct
26 Correct 440 ms 9316 KB Output is correct
27 Correct 420 ms 9512 KB Output is correct
28 Correct 317 ms 10352 KB Output is correct
29 Correct 444 ms 9596 KB Output is correct
30 Correct 312 ms 10216 KB Output is correct
31 Correct 407 ms 9464 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 3240 KB Output is correct
4 Incorrect 5 ms 3064 KB Output isn't correct
5 Halted 0 ms 0 KB -