Submission #82496

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82496	2018-10-31T05:40:30 Z	Good	Evacuation plan (IZhO18_plan)	C++11	41 / 100	4000 ms	48360 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 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 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}});
				p[dsu (nd)] = dsu (i.ff);
				dfs (i.ff, x);
			}		
			
		}
		
		else {
			if (x <= dis[i.ff])
				p[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, p[i] = i;

	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));
		
		for (int i = 1; i <= n; i++)
			p[i] = i;
		
		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);
						p[dsu(d.ss.ff)] = dsu (d.ss.ss);
						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:97: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:101: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:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &k);
  ~~~~~~^~~~~~~~~~
plan.cpp:112: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:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &Q);
  ~~~~~~^~~~~~~~~~
plan.cpp:117: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	2808 KB	Output is correct
2	Correct	7 ms	2936 KB	Output is correct
3	Correct	7 ms	2936 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	7 ms	2936 KB	Output is correct
6	Correct	6 ms	2936 KB	Output is correct
7	Correct	5 ms	2812 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	9 ms	2936 KB	Output is correct
10	Correct	7 ms	2976 KB	Output is correct
11	Correct	9 ms	2936 KB	Output is correct
12	Correct	7 ms	2936 KB	Output is correct
13	Correct	9 ms	2808 KB	Output is correct
14	Correct	9 ms	2936 KB	Output is correct
15	Correct	9 ms	2936 KB	Output is correct

Subtask #2

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	7 ms	2936 KB	Output is correct
3	Correct	7 ms	2936 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	7 ms	2936 KB	Output is correct
6	Correct	6 ms	2936 KB	Output is correct
7	Correct	5 ms	2812 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	9 ms	2936 KB	Output is correct
10	Correct	7 ms	2976 KB	Output is correct
11	Correct	9 ms	2936 KB	Output is correct
12	Correct	7 ms	2936 KB	Output is correct
13	Correct	9 ms	2808 KB	Output is correct
14	Correct	9 ms	2936 KB	Output is correct
15	Correct	9 ms	2936 KB	Output is correct
16	Correct	1319 ms	14180 KB	Output is correct
17	Execution timed out	4072 ms	48360 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2872 KB	Output is correct
2	Correct	4 ms	2808 KB	Output is correct
3	Correct	4 ms	2812 KB	Output is correct
4	Correct	5 ms	2780 KB	Output is correct
5	Correct	5 ms	2876 KB	Output is correct
6	Correct	4 ms	2808 KB	Output is correct
7	Correct	5 ms	2780 KB	Output is correct
8	Correct	4 ms	2844 KB	Output is correct
9	Correct	4 ms	2812 KB	Output is correct
10	Correct	5 ms	2808 KB	Output is correct

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	687 ms	20196 KB	Output is correct
2	Correct	2966 ms	41724 KB	Output is correct
3	Correct	2711 ms	40084 KB	Output is correct
4	Correct	315 ms	18048 KB	Output is correct
5	Correct	1207 ms	30556 KB	Output is correct
6	Correct	1735 ms	41016 KB	Output is correct
7	Correct	2827 ms	40788 KB	Output is correct
8	Correct	2170 ms	40528 KB	Output is correct
9	Correct	2332 ms	41308 KB	Output is correct
10	Correct	2786 ms	41180 KB	Output is correct
11	Correct	1774 ms	34084 KB	Output is correct
12	Correct	2508 ms	38992 KB	Output is correct
13	Correct	2530 ms	41400 KB	Output is correct
14	Correct	2753 ms	38684 KB	Output is correct
15	Correct	2560 ms	40724 KB	Output is correct
16	Correct	2902 ms	40668 KB	Output is correct
17	Correct	1689 ms	40416 KB	Output is correct
18	Correct	2627 ms	40540 KB	Output is correct
19	Correct	89 ms	10744 KB	Output is correct
20	Correct	2017 ms	40248 KB	Output is correct
21	Correct	740 ms	29748 KB	Output is correct
22	Correct	197 ms	10344 KB	Output is correct
23	Correct	172 ms	9208 KB	Output is correct
24	Correct	150 ms	9476 KB	Output is correct
25	Correct	166 ms	10220 KB	Output is correct
26	Correct	141 ms	10360 KB	Output is correct
27	Correct	250 ms	18044 KB	Output is correct
28	Correct	143 ms	9536 KB	Output is correct
29	Correct	250 ms	18296 KB	Output is correct
30	Correct	141 ms	9552 KB	Output is correct
31	Correct	227 ms	18064 KB	Output is correct

Subtask #5

0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	7 ms	2936 KB	Output is correct
3	Correct	7 ms	2936 KB	Output is correct
4	Correct	4 ms	2808 KB	Output is correct
5	Correct	7 ms	2936 KB	Output is correct
6	Correct	6 ms	2936 KB	Output is correct
7	Correct	5 ms	2812 KB	Output is correct
8	Correct	4 ms	2808 KB	Output is correct
9	Correct	9 ms	2936 KB	Output is correct
10	Correct	7 ms	2976 KB	Output is correct
11	Correct	9 ms	2936 KB	Output is correct
12	Correct	7 ms	2936 KB	Output is correct
13	Correct	9 ms	2808 KB	Output is correct
14	Correct	9 ms	2936 KB	Output is correct
15	Correct	9 ms	2936 KB	Output is correct
16	Correct	1319 ms	14180 KB	Output is correct
17	Execution timed out	4072 ms	48360 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-