Submission #82500

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82500	2018-10-31T06:20:24 Z	Good	Evacuation plan (IZhO18_plan)	C++11	41 / 100	4000 ms	49848 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3236 KB	Output is correct
2	Correct	8 ms	3320 KB	Output is correct
3	Correct	8 ms	3320 KB	Output is correct
4	Correct	5 ms	3192 KB	Output is correct
5	Correct	8 ms	3320 KB	Output is correct
6	Correct	8 ms	3320 KB	Output is correct
7	Correct	5 ms	3192 KB	Output is correct
8	Correct	5 ms	3192 KB	Output is correct
9	Correct	10 ms	3320 KB	Output is correct
10	Correct	8 ms	3320 KB	Output is correct
11	Correct	10 ms	3320 KB	Output is correct
12	Correct	8 ms	3292 KB	Output is correct
13	Correct	10 ms	3324 KB	Output is correct
14	Correct	10 ms	3320 KB	Output is correct
15	Correct	10 ms	3320 KB	Output is correct

Subtask #2

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3236 KB	Output is correct
2	Correct	8 ms	3320 KB	Output is correct
3	Correct	8 ms	3320 KB	Output is correct
4	Correct	5 ms	3192 KB	Output is correct
5	Correct	8 ms	3320 KB	Output is correct
6	Correct	8 ms	3320 KB	Output is correct
7	Correct	5 ms	3192 KB	Output is correct
8	Correct	5 ms	3192 KB	Output is correct
9	Correct	10 ms	3320 KB	Output is correct
10	Correct	8 ms	3320 KB	Output is correct
11	Correct	10 ms	3320 KB	Output is correct
12	Correct	8 ms	3292 KB	Output is correct
13	Correct	10 ms	3324 KB	Output is correct
14	Correct	10 ms	3320 KB	Output is correct
15	Correct	10 ms	3320 KB	Output is correct
16	Correct	1282 ms	14680 KB	Output is correct
17	Execution timed out	4054 ms	49848 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3192 KB	Output is correct
2	Correct	5 ms	3192 KB	Output is correct
3	Correct	5 ms	3192 KB	Output is correct
4	Correct	5 ms	3164 KB	Output is correct
5	Correct	5 ms	3192 KB	Output is correct
6	Correct	5 ms	3192 KB	Output is correct
7	Correct	6 ms	3164 KB	Output is correct
8	Correct	5 ms	3192 KB	Output is correct
9	Correct	5 ms	3192 KB	Output is correct
10	Correct	5 ms	3192 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	731 ms	20436 KB	Output is correct
2	Correct	3105 ms	41728 KB	Output is correct
3	Correct	2612 ms	39824 KB	Output is correct
4	Correct	257 ms	18092 KB	Output is correct
5	Correct	1188 ms	30192 KB	Output is correct
6	Correct	1682 ms	40748 KB	Output is correct
7	Correct	2822 ms	40788 KB	Output is correct
8	Correct	2124 ms	40228 KB	Output is correct
9	Correct	2469 ms	41228 KB	Output is correct
10	Correct	2720 ms	41076 KB	Output is correct
11	Correct	1729 ms	33924 KB	Output is correct
12	Correct	2743 ms	38884 KB	Output is correct
13	Correct	2567 ms	40900 KB	Output is correct
14	Correct	2688 ms	38424 KB	Output is correct
15	Correct	2528 ms	40412 KB	Output is correct
16	Correct	3129 ms	40496 KB	Output is correct
17	Correct	1721 ms	40412 KB	Output is correct
18	Correct	2470 ms	40248 KB	Output is correct
19	Correct	100 ms	11084 KB	Output is correct
20	Correct	2124 ms	39860 KB	Output is correct
21	Correct	742 ms	29476 KB	Output is correct
22	Correct	183 ms	10484 KB	Output is correct
23	Correct	215 ms	9500 KB	Output is correct
24	Correct	146 ms	9608 KB	Output is correct
25	Correct	236 ms	10232 KB	Output is correct
26	Correct	183 ms	10128 KB	Output is correct
27	Correct	341 ms	18096 KB	Output is correct
28	Correct	146 ms	9604 KB	Output is correct
29	Correct	286 ms	18140 KB	Output is correct
30	Correct	152 ms	9676 KB	Output is correct
31	Correct	302 ms	18200 KB	Output is correct

Subtask #5

0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3236 KB	Output is correct
2	Correct	8 ms	3320 KB	Output is correct
3	Correct	8 ms	3320 KB	Output is correct
4	Correct	5 ms	3192 KB	Output is correct
5	Correct	8 ms	3320 KB	Output is correct
6	Correct	8 ms	3320 KB	Output is correct
7	Correct	5 ms	3192 KB	Output is correct
8	Correct	5 ms	3192 KB	Output is correct
9	Correct	10 ms	3320 KB	Output is correct
10	Correct	8 ms	3320 KB	Output is correct
11	Correct	10 ms	3320 KB	Output is correct
12	Correct	8 ms	3292 KB	Output is correct
13	Correct	10 ms	3324 KB	Output is correct
14	Correct	10 ms	3320 KB	Output is correct
15	Correct	10 ms	3320 KB	Output is correct
16	Correct	1282 ms	14680 KB	Output is correct
17	Execution timed out	4054 ms	49848 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-