Submission #82500

#	Time	Username	Problem	Language	Result	Execution time	Memory
82500		Good	Evacuation plan (IZhO18_plan)	C++11	41 / 100	4054 ms	49848 KiB

plan

/*
ID: blackha5
TASK: test
LANG: C++
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define ff first
#define ss second
#define Maxn 100003
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
#define tr(i, c) for(__typeof(c).begin() i = (c).begin() ; i != (c).end() ; i++)
using namespace std;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> order;

bool vis[Maxn];
bool vis1[Maxn];

int p[Maxn];
int ans[Maxn];
int cnt[Maxn];
int dis[Maxn];
int a[Maxn * 5];
int b[Maxn * 5];
int n, m, k, g, Q;
int L[Maxn], R[Maxn];

set <pair <int, pii> > s;
vector <pii> adj[Maxn];
priority_queue <pii, vector <pii>, greater <pii> > q;

void dij () {
	while (!q.empty()) {
		pii x = q.top();
		q.pop();
		
		if (vis[x.ss])
			continue;
			
		vis[x.ss] = 1;	
		for (auto i: adj[x.ss]) {
			dis[i.ff] = min (dis[i.ff], x.ff + i.ss);
			q.push ({dis[i.ff], i.ff});	
		}
	}
}

int dsu (int x) {
	while (p[x] == x)
		return x;
		
	return p[x] = dsu (p[x]);
}

void uni (int x, int y) {
	if (cnt[x] < cnt[y])
		cnt[y] += cnt[x], p[x] = y;
	else
		cnt[x] += cnt[y], p[y] = x;	
}

void dfs (int nd, int x) {
	if (vis1[nd])
		return;
		
	vis1[nd] = 1;
	
	for (auto i: adj[nd]) {
		if (!vis1[i.ff]) {
			if (x > dis[i.ff])
				s.insert ({dis[i.ff], {nd, i.ff}});
			else {
				s.erase ({dis[i.ff], {nd, i.ff}});
				uni (dsu (i.ff), dsu (nd));
				dfs (i.ff, x);
			}		
			
		}
		
		else {
			if (x <= dis[i.ff])
				uni (dsu (nd), dsu (i.ff));
			else
				s.insert ({dis[i.ff], {nd, i.ff}});
		}
	}
}

int main () {
	//freopen ("file.in", "r", stdin);
	//freopen ("file.out", "w", stdout);
	
 	//srand ((unsigned) time ( NULL ));
	//int randomNumber = rand() % 10 + 1;

	scanf ("%d%d", &n, &m);
	
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf ("%d%d%d", &u, &v, &w);
		
		adj[u].pb ({v, w});
		adj[v].pb ({u, w});
	}	

	for (int i = 1; i <= n; i++)
		dis[i] = Inf;

	scanf ("%d", &k);
	for (int i = 1; i <= k; i++)
		scanf ("%d", &g), dis[g] = 0, q.push ({0, g});

	dij();
	scanf ("%d", &Q);
	for (int i = 1; i <= Q; i++) {
		scanf ("%d%d", &a[i], &b[i]);
		L[i] = 0;
		R[i] = 1e9;
	}	
	
	while (1) {
		s.clear();
		memset (vis1, 0, sizeof (vis1));
		memset (cnt, 0, sizeof (cnt));
		
		for (int i = 1; i <= n; i++)
			p[i] = i, cnt[i] = 1;
		
		vector <pii> v;
		for (int i = 1; i <= Q; i++) {
			if (L[i] <= R[i])
				v.pb ({mid (L[i], R[i]), i});	
		}	
	
		if (!v.size())
			break;
		
		sort (all(v));
		reverse (all(v));
		
		for (auto i: v) {
			while (1) {
				if (s.size() > 0) {
					pair <int, pii> d = *s.rbegin();
					if (i.ff <= d.ff) {
						s.erase (d);
						uni (dsu (d.ss.ss), dsu (d.ss.ff));
						dfs (d.ss.ss, i.ff);
					}	
					else
						break;	
				}
				else
					break;
			}
			
			if (!vis1[a[i.ss]] and i.ff <= dis[a[i.ss]])
				dfs (a[i.ss], i.ff);	
												
			if (p[dsu(a[i.ss])] == p[dsu(b[i.ss])])
				ans[i.ss] = i.ff, L[i.ss] = i.ff + 1;
			
			else
				R[i.ss] = i.ff - 1;		
		}
	}
	
	for (int i = 1; i <= Q; i++)
		printf ("%d\n", ans[i]);
		
	return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
plan.cpp:109:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d%d", &u, &v, &w);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &k);
  ~~~~~~^~~~~~~~~~
plan.cpp:120:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &g), dis[g] = 0, q.push ({0, g});
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &Q);
  ~~~~~~^~~~~~~~~~
plan.cpp:125:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a[i], &b[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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