Submission #167607

#	Time	Username	Problem	Language	Result	Execution time	Memory
167607		Trickster	Evacuation plan (IZhO18_plan)	C++14	0 / 100	1333 ms	11764 KiB

plan

//Suleyman Atayew

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

#define N 100010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define inf 1000000007
#define pii pair <int, int>

using namespace std;

pii T[N];
int dis[N];
int vis[N];
int a, b, c;
int n, m, k, q;
vector <pii> E[N];
int A[N], L[N], R[N], Pr[N];
priority_queue <pii, vector <pii>, greater <pii>> Q;

int ata(int x)
{
	if(Pr[x] == x) return x;
	
	return Pr[x] = ata(Pr[x]);
}
void uni(int a, int b)
{
	a = ata(a);
	b = ata(b);
	
	if(a == b) return;
	
	Pr[b] = a;
}

int main()
{
	cin >> n >> m;
	
	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 <= n; i++) dis[i] = 1e9;
	
	for(int i = 1; i <= k; i++) {
		cin >> a;
		
		dis[a] = 0, Q.push({0, a});
	}
	
	while(!Q.empty()) {
		int nd = Q.top().ss;
		Q.pop();
		
		if(vis[nd] == 1) continue;
		
		vis[nd] = 1;
		for(auto i: E[nd]) {
			int to = i.ff;
			int yol = i.ss;
			
			if(dis[to] > dis[nd] + yol)
				dis[to] = dis[nd] + yol, Q.push({dis[to], to});
		}
	}
	
	pii arr[N];
	for(int i = 1; i <= n; i++) arr[i] = {dis[i], i};
	sort(arr + 1, arr + n + 1);
	
	cin >> q;
	
	for(int i = 1; i <= q; i++) {
		cin >> a >> b;
		
		T[i] = {a, b};
		L[i] = 1, R[i] = 15;
	}
	
	for(int i = 1; i <= 30; i++) {
		vector <pii> MD;
		
		for(int h = 1; h <= q; h++) {
			if(R[h] < L[h]) continue;
			
			MD.pb({(L[h] + R[h]) / 2, h});
		}
		
		sort(MD.begin(), MD.end());
		reverse(MD.begin(), MD.end());
		
		memset(vis, 0, sizeof(vis));
		
		for(int h = 1; h <= n; h++) Pr[h] = h;
		
		int x = 0;
		for(int h = n; h >= 1; h--) {
			while(x < MD.size() && MD[x].ff > arr[h].ff) {
				int j = MD[x].ss;
				int md = MD[x].ff;
				
				int a = ata(T[j].ff);
				int b = ata(T[j].ss);
				
				if(a == b) {
					L[j] = md+1;
					A[j] = md;
				}
				else R[j] = md-1;
				
				x++;
			}
			
			int nd = arr[h].ss;
			
			for(auto j: E[nd])
				if(vis[j.ff] == 1) uni(j.ff, nd);
			
			vis[nd] = 1;
		}
		
		while(x < MD.size()) {
			int j = MD[x].ss;
			int md = MD[x].ff;
			
			int a = ata(T[j].ff);
			int b = ata(T[j].ss);
			
			if(a == b) {
				L[j] = md+1;
				A[j] = md;
			}
			else R[j] = md-1;
			
			x++;
		}
	}
	for(int i = 1; i <= q; i++) cout << A[i] << "\n";
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:116:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(x < MD.size() && MD[x].ff > arr[h].ff) {
          ~~^~~~~~~~~~~
plan.cpp:140:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(x < MD.size()) {
         ~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46