oj.uz

Submission #42499

# Submission time Handle Problem Language Result Execution time Memory
42499 2018-02-27T22:54:00 Z MatheusLealV Evacuation plan (IZhO18_plan) C++14
100 / 100
 856 ms 58784 KB 
#include <bits/stdc++.h>
#define int long long
#define N 100005
#define inf 2000000000000000000LL
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, m, k, q, P[N], id[N], dist[N], rev[N], pai[N], peso[N];

vector<pii> grafo[N];

list<int> l[N], comp_hist[N];

list<pii> hist[N];

void dijkstra()
{
	priority_queue<pii, vector<pii>, greater<pii> > pq;

	for(int i = 1; i <= n; i++) dist[i] = inf;

	for(int i = 1; i <= k; i++) dist[ P[i] ] = 0, pq.push({0, P[i]});

	while(!pq.empty())
	{
		int x = pq.top().s, d = pq.top().f;

		pq.pop();

		if(d > dist[x]) continue;

		for(auto v: grafo[x])
		{
			if(dist[v.f] > dist[x] + v.s)
			{
				dist[v.f] = dist[x] + v.s;

				pq.push({dist[v.f], v.f});
			}
		}
	}

	vector<pii> v;

	for(int i = 1; i <= n; i++) v.push_back({dist[i], i});

	sort(v.begin(), v.end());

	for(int i = 0; i < v.size(); i++) id[ v[i].s ] = i + 1, rev[i + 1] = v[i].s;
}

void persistent_join(int a, int b, int t)
{
	a = pai[a], b = pai[b];

	if(a != b)
	{
        if(peso[a] > peso[b]) swap(a, b);

        for(auto it = l[a].begin(); it != l[a].end(); it++)
        {
                hist[*it].push_back(pii(t, b));

                pai[*it] = b;
        }

        peso[b] += peso[a];

        comp_hist[b].push_back(t);

        l[b].splice(l[b].end(), l[a]);
	}
}

int p_query(int a, int b)
{
	int ans = 0;

	for(auto x: hist[a])
	{
		for(auto y: hist[b])
		{
			if(x.s == y.s)
			{
				ans = max(ans, min(x.f, y.f));
			}
		}
	}

	return ans;
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1, a, b, c; i <= m; i++)
	{
		cin>>a>>b>>c;

		grafo[a].push_back({b, c});

		grafo[b].push_back({a, c});
	}

	cin>>k;

	for(int i = 1; i <= k; i++) cin>>P[i];

	dijkstra();

    for(int i = 1; i <= n; i++)
    {
        l[i].push_back(i);

        hist[i].push_back(pii(dist[i], i));

        comp_hist[i].push_back(i);

        peso[i] = 1, pai[i] = i;
    }

	for(int x = n; x >= 1; x--)
	{
		int xi = rev[x];

		for(auto v: grafo[xi])
		{
			if(id[v.f] > x)
			{
				persistent_join(v.f, xi, dist[xi]);
			}
		}
	}

	cin>>q;

	for(int t = 1, a, b; t <= q; t++)
	{
		cin>>a>>b;

		int ini = 1, fim = n, mid, best = -1;

		cout<<p_query(a, b)<<"\n";
	}
}

Compilation message

plan.cpp: In function 'void dijkstra()':
plan.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) id[ v[i].s ] = i + 1, rev[i + 1] = v[i].s;
                 ~~^~~~~~~~~~
plan.cpp: In function 'int32_t main()':
plan.cpp:147:7: warning: unused variable 'ini' [-Wunused-variable]
   int ini = 1, fim = n, mid, best = -1;
       ^~~
plan.cpp:147:16: warning: unused variable 'fim' [-Wunused-variable]
   int ini = 1, fim = n, mid, best = -1;
                ^~~
plan.cpp:147:25: warning: unused variable 'mid' [-Wunused-variable]
   int ini = 1, fim = n, mid, best = -1;
                         ^~~
plan.cpp:147:30: warning: unused variable 'best' [-Wunused-variable]
   int ini = 1, fim = n, mid, best = -1;
                              ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9724 KB Output is correct
2 Correct 12 ms 9976 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 12 ms 10072 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 13 ms 10108 KB Output is correct
10 Correct 15 ms 10104 KB Output is correct
11 Correct 12 ms 10104 KB Output is correct
12 Correct 12 ms 10108 KB Output is correct
13 Correct 12 ms 10104 KB Output is correct
14 Correct 12 ms 10104 KB Output is correct
15 Correct 14 ms 10104 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9724 KB Output is correct
2 Correct 12 ms 9976 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 12 ms 10072 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 13 ms 10108 KB Output is correct
10 Correct 15 ms 10104 KB Output is correct
11 Correct 12 ms 10104 KB Output is correct
12 Correct 12 ms 10108 KB Output is correct
13 Correct 12 ms 10104 KB Output is correct
14 Correct 12 ms 10104 KB Output is correct
15 Correct 14 ms 10104 KB Output is correct
16 Correct 296 ms 35772 KB Output is correct
17 Correct 707 ms 58168 KB Output is correct
18 Correct 51 ms 15160 KB Output is correct
19 Correct 277 ms 38176 KB Output is correct
20 Correct 719 ms 58408 KB Output is correct
21 Correct 465 ms 45940 KB Output is correct
22 Correct 279 ms 38904 KB Output is correct
23 Correct 752 ms 58388 KB Output is correct
24 Correct 687 ms 58720 KB Output is correct
25 Correct 705 ms 58784 KB Output is correct
26 Correct 274 ms 38796 KB Output is correct
27 Correct 267 ms 39132 KB Output is correct
28 Correct 268 ms 39024 KB Output is correct
29 Correct 272 ms 39324 KB Output is correct
30 Correct 264 ms 39296 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9840 KB Output is correct
2 Correct 9 ms 9720 KB Output is correct
3 Correct 10 ms 9720 KB Output is correct
4 Correct 10 ms 9724 KB Output is correct
5 Correct 10 ms 9704 KB Output is correct
6 Correct 11 ms 9720 KB Output is correct
7 Correct 10 ms 9720 KB Output is correct
8 Correct 10 ms 9692 KB Output is correct
9 Correct 10 ms 9704 KB Output is correct
10 Correct 10 ms 9724 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 44112 KB Output is correct
2 Correct 629 ms 56920 KB Output is correct
3 Correct 638 ms 57220 KB Output is correct
4 Correct 215 ms 39880 KB Output is correct
5 Correct 640 ms 57352 KB Output is correct
6 Correct 622 ms 57368 KB Output is correct
7 Correct 635 ms 57108 KB Output is correct
8 Correct 633 ms 57308 KB Output is correct
9 Correct 613 ms 57000 KB Output is correct
10 Correct 611 ms 56912 KB Output is correct
11 Correct 617 ms 56980 KB Output is correct
12 Correct 631 ms 56892 KB Output is correct
13 Correct 637 ms 56984 KB Output is correct
14 Correct 674 ms 57028 KB Output is correct
15 Correct 670 ms 57100 KB Output is correct
16 Correct 652 ms 57116 KB Output is correct
17 Correct 624 ms 56980 KB Output is correct
18 Correct 607 ms 57064 KB Output is correct
19 Correct 181 ms 37648 KB Output is correct
20 Correct 620 ms 57160 KB Output is correct
21 Correct 561 ms 57908 KB Output is correct
22 Correct 204 ms 37428 KB Output is correct
23 Correct 298 ms 51184 KB Output is correct
24 Correct 263 ms 37396 KB Output is correct
25 Correct 210 ms 37400 KB Output is correct
26 Correct 340 ms 52456 KB Output is correct
27 Correct 201 ms 39740 KB Output is correct
28 Correct 206 ms 37740 KB Output is correct
29 Correct 201 ms 39736 KB Output is correct
30 Correct 204 ms 37532 KB Output is correct
31 Correct 200 ms 39864 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9724 KB Output is correct
2 Correct 12 ms 9976 KB Output is correct
3 Correct 12 ms 9976 KB Output is correct
4 Correct 10 ms 9720 KB Output is correct
5 Correct 12 ms 10072 KB Output is correct
6 Correct 12 ms 9976 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 13 ms 10108 KB Output is correct
10 Correct 15 ms 10104 KB Output is correct
11 Correct 12 ms 10104 KB Output is correct
12 Correct 12 ms 10108 KB Output is correct
13 Correct 12 ms 10104 KB Output is correct
14 Correct 12 ms 10104 KB Output is correct
15 Correct 14 ms 10104 KB Output is correct
16 Correct 296 ms 35772 KB Output is correct
17 Correct 707 ms 58168 KB Output is correct
18 Correct 51 ms 15160 KB Output is correct
19 Correct 277 ms 38176 KB Output is correct
20 Correct 719 ms 58408 KB Output is correct
21 Correct 465 ms 45940 KB Output is correct
22 Correct 279 ms 38904 KB Output is correct
23 Correct 752 ms 58388 KB Output is correct
24 Correct 687 ms 58720 KB Output is correct
25 Correct 705 ms 58784 KB Output is correct
26 Correct 274 ms 38796 KB Output is correct
27 Correct 267 ms 39132 KB Output is correct
28 Correct 268 ms 39024 KB Output is correct
29 Correct 272 ms 39324 KB Output is correct
30 Correct 264 ms 39296 KB Output is correct
31 Correct 10 ms 9840 KB Output is correct
32 Correct 9 ms 9720 KB Output is correct
33 Correct 10 ms 9720 KB Output is correct
34 Correct 10 ms 9724 KB Output is correct
35 Correct 10 ms 9704 KB Output is correct
36 Correct 11 ms 9720 KB Output is correct
37 Correct 10 ms 9720 KB Output is correct
38 Correct 10 ms 9692 KB Output is correct
39 Correct 10 ms 9704 KB Output is correct
40 Correct 10 ms 9724 KB Output is correct
41 Correct 373 ms 44112 KB Output is correct
42 Correct 629 ms 56920 KB Output is correct
43 Correct 638 ms 57220 KB Output is correct
44 Correct 215 ms 39880 KB Output is correct
45 Correct 640 ms 57352 KB Output is correct
46 Correct 622 ms 57368 KB Output is correct
47 Correct 635 ms 57108 KB Output is correct
48 Correct 633 ms 57308 KB Output is correct
49 Correct 613 ms 57000 KB Output is correct
50 Correct 611 ms 56912 KB Output is correct
51 Correct 617 ms 56980 KB Output is correct
52 Correct 631 ms 56892 KB Output is correct
53 Correct 637 ms 56984 KB Output is correct
54 Correct 674 ms 57028 KB Output is correct
55 Correct 670 ms 57100 KB Output is correct
56 Correct 652 ms 57116 KB Output is correct
57 Correct 624 ms 56980 KB Output is correct
58 Correct 607 ms 57064 KB Output is correct
59 Correct 181 ms 37648 KB Output is correct
60 Correct 620 ms 57160 KB Output is correct
61 Correct 561 ms 57908 KB Output is correct
62 Correct 204 ms 37428 KB Output is correct
63 Correct 298 ms 51184 KB Output is correct
64 Correct 263 ms 37396 KB Output is correct
65 Correct 210 ms 37400 KB Output is correct
66 Correct 340 ms 52456 KB Output is correct
67 Correct 201 ms 39740 KB Output is correct
68 Correct 206 ms 37740 KB Output is correct
69 Correct 201 ms 39736 KB Output is correct
70 Correct 204 ms 37532 KB Output is correct
71 Correct 200 ms 39864 KB Output is correct
72 Correct 460 ms 45528 KB Output is correct
73 Correct 700 ms 57732 KB Output is correct
74 Correct 699 ms 57792 KB Output is correct
75 Correct 701 ms 58168 KB Output is correct
76 Correct 767 ms 57976 KB Output is correct
77 Correct 707 ms 57348 KB Output is correct
78 Correct 758 ms 57404 KB Output is correct
79 Correct 856 ms 57412 KB Output is correct
80 Correct 770 ms 57172 KB Output is correct
81 Correct 771 ms 57436 KB Output is correct
82 Correct 713 ms 57092 KB Output is correct
83 Correct 751 ms 57116 KB Output is correct
84 Correct 706 ms 57352 KB Output is correct
85 Correct 694 ms 57652 KB Output is correct
86 Correct 682 ms 57264 KB Output is correct
87 Correct 680 ms 57340 KB Output is correct
88 Correct 692 ms 57460 KB Output is correct
89 Correct 268 ms 38476 KB Output is correct
90 Correct 702 ms 57680 KB Output is correct
91 Correct 620 ms 58044 KB Output is correct
92 Correct 279 ms 37948 KB Output is correct
93 Correct 423 ms 52152 KB Output is correct
94 Correct 279 ms 38060 KB Output is correct
95 Correct 270 ms 37952 KB Output is correct
96 Correct 496 ms 53680 KB Output is correct
97 Correct 293 ms 40624 KB Output is correct
98 Correct 272 ms 37864 KB Output is correct
99 Correct 294 ms 40572 KB Output is correct
100 Correct 276 ms 38044 KB Output is correct