oj.uz

Submission #82603

# Submission time Handle Problem Language Result Execution time Memory
82603 2018-10-31T18:17:05 Z Good Evacuation plan (IZhO18_plan) C++11
19 / 100
 3205 ms 20768 KB 
#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 ans[N];
int Par[N];
int L[N], R[N];
int v[N], vis[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++)
		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) {
		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] == 1) 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 9 ms 3192 KB Output is correct
3 Correct 9 ms 3192 KB Output is correct
4 Incorrect 6 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 9 ms 3192 KB Output is correct
3 Correct 9 ms 3192 KB Output is correct
4 Incorrect 6 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 3168 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 1514 ms 12604 KB Output is correct
2 Correct 3136 ms 20664 KB Output is correct
3 Correct 3170 ms 20716 KB Output is correct
4 Correct 459 ms 9576 KB Output is correct
5 Correct 3183 ms 20612 KB Output is correct
6 Correct 3143 ms 20608 KB Output is correct
7 Correct 3175 ms 20632 KB Output is correct
8 Correct 3205 ms 20588 KB Output is correct
9 Correct 3179 ms 20720 KB Output is correct
10 Correct 3150 ms 20572 KB Output is correct
11 Correct 3194 ms 20768 KB Output is correct
12 Correct 3105 ms 20660 KB Output is correct
13 Correct 3157 ms 20588 KB Output is correct
14 Correct 3193 ms 20604 KB Output is correct
15 Correct 3139 ms 20764 KB Output is correct
16 Correct 3199 ms 20720 KB Output is correct
17 Correct 3186 ms 20636 KB Output is correct
18 Correct 3172 ms 20592 KB Output is correct
19 Correct 343 ms 9116 KB Output is correct
20 Correct 3171 ms 20540 KB Output is correct
21 Correct 2671 ms 20288 KB Output is correct
22 Correct 312 ms 10408 KB Output is correct
23 Correct 360 ms 9080 KB Output is correct
24 Correct 314 ms 10336 KB Output is correct
25 Correct 318 ms 10212 KB Output is correct
26 Correct 394 ms 9260 KB Output is correct
27 Correct 430 ms 9356 KB Output is correct
28 Correct 310 ms 10212 KB Output is correct
29 Correct 394 ms 9348 KB Output is correct
30 Correct 310 ms 10220 KB Output is correct
31 Correct 479 ms 9276 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 9 ms 3192 KB Output is correct
3 Correct 9 ms 3192 KB Output is correct
4 Incorrect 6 ms 3064 KB Output isn't correct
5 Halted 0 ms 0 KB -