답안 #42500 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42500	2018-02-27T22:56:30 Z	MatheusLealV	Evacuation plan (IZhO18_plan)	C++14	100 / 100	730 ms	49596 KB

plan

#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];

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];

        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));

        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;

		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;
                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7672 KB	Output is correct
3	Correct	9 ms	7672 KB	Output is correct
4	Correct	8 ms	7416 KB	Output is correct
5	Correct	9 ms	7644 KB	Output is correct
6	Correct	9 ms	7544 KB	Output is correct
7	Correct	8 ms	7416 KB	Output is correct
8	Correct	7 ms	7416 KB	Output is correct
9	Correct	9 ms	7672 KB	Output is correct
10	Correct	10 ms	7644 KB	Output is correct
11	Correct	9 ms	7676 KB	Output is correct
12	Correct	9 ms	7700 KB	Output is correct
13	Correct	9 ms	7672 KB	Output is correct
14	Correct	10 ms	7672 KB	Output is correct
15	Correct	10 ms	7644 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7672 KB	Output is correct
3	Correct	9 ms	7672 KB	Output is correct
4	Correct	8 ms	7416 KB	Output is correct
5	Correct	9 ms	7644 KB	Output is correct
6	Correct	9 ms	7544 KB	Output is correct
7	Correct	8 ms	7416 KB	Output is correct
8	Correct	7 ms	7416 KB	Output is correct
9	Correct	9 ms	7672 KB	Output is correct
10	Correct	10 ms	7644 KB	Output is correct
11	Correct	9 ms	7676 KB	Output is correct
12	Correct	9 ms	7700 KB	Output is correct
13	Correct	9 ms	7672 KB	Output is correct
14	Correct	10 ms	7672 KB	Output is correct
15	Correct	10 ms	7644 KB	Output is correct
16	Correct	249 ms	28732 KB	Output is correct
17	Correct	665 ms	48696 KB	Output is correct
18	Correct	47 ms	12020 KB	Output is correct
19	Correct	257 ms	29492 KB	Output is correct
20	Correct	676 ms	48920 KB	Output is correct
21	Correct	404 ms	36496 KB	Output is correct
22	Correct	228 ms	29828 KB	Output is correct
23	Correct	684 ms	48904 KB	Output is correct
24	Correct	651 ms	49220 KB	Output is correct
25	Correct	646 ms	48764 KB	Output is correct
26	Correct	244 ms	28780 KB	Output is correct
27	Correct	236 ms	28832 KB	Output is correct
28	Correct	240 ms	28704 KB	Output is correct
29	Correct	236 ms	28828 KB	Output is correct
30	Correct	249 ms	29004 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	8 ms	7416 KB	Output is correct
3	Correct	8 ms	7416 KB	Output is correct
4	Correct	8 ms	7416 KB	Output is correct
5	Correct	8 ms	7340 KB	Output is correct
6	Correct	8 ms	7416 KB	Output is correct
7	Correct	8 ms	7416 KB	Output is correct
8	Correct	8 ms	7372 KB	Output is correct
9	Correct	8 ms	7416 KB	Output is correct
10	Correct	8 ms	7432 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	339 ms	35172 KB	Output is correct
2	Correct	685 ms	47712 KB	Output is correct
3	Correct	624 ms	47804 KB	Output is correct
4	Correct	194 ms	30908 KB	Output is correct
5	Correct	612 ms	47692 KB	Output is correct
6	Correct	590 ms	47704 KB	Output is correct
7	Correct	566 ms	47800 KB	Output is correct
8	Correct	595 ms	47876 KB	Output is correct
9	Correct	584 ms	47692 KB	Output is correct
10	Correct	589 ms	47864 KB	Output is correct
11	Correct	587 ms	47800 KB	Output is correct
12	Correct	591 ms	47680 KB	Output is correct
13	Correct	585 ms	47752 KB	Output is correct
14	Correct	566 ms	47888 KB	Output is correct
15	Correct	593 ms	47900 KB	Output is correct
16	Correct	593 ms	47752 KB	Output is correct
17	Correct	599 ms	47740 KB	Output is correct
18	Correct	604 ms	47708 KB	Output is correct
19	Correct	162 ms	28472 KB	Output is correct
20	Correct	610 ms	47748 KB	Output is correct
21	Correct	532 ms	48416 KB	Output is correct
22	Correct	185 ms	28464 KB	Output is correct
23	Correct	262 ms	42296 KB	Output is correct
24	Correct	182 ms	28560 KB	Output is correct
25	Correct	263 ms	28524 KB	Output is correct
26	Correct	385 ms	43244 KB	Output is correct
27	Correct	258 ms	31032 KB	Output is correct
28	Correct	187 ms	28588 KB	Output is correct
29	Correct	188 ms	31008 KB	Output is correct
30	Correct	192 ms	28572 KB	Output is correct
31	Correct	190 ms	30992 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7416 KB	Output is correct
2	Correct	9 ms	7672 KB	Output is correct
3	Correct	9 ms	7672 KB	Output is correct
4	Correct	8 ms	7416 KB	Output is correct
5	Correct	9 ms	7644 KB	Output is correct
6	Correct	9 ms	7544 KB	Output is correct
7	Correct	8 ms	7416 KB	Output is correct
8	Correct	7 ms	7416 KB	Output is correct
9	Correct	9 ms	7672 KB	Output is correct
10	Correct	10 ms	7644 KB	Output is correct
11	Correct	9 ms	7676 KB	Output is correct
12	Correct	9 ms	7700 KB	Output is correct
13	Correct	9 ms	7672 KB	Output is correct
14	Correct	10 ms	7672 KB	Output is correct
15	Correct	10 ms	7644 KB	Output is correct
16	Correct	249 ms	28732 KB	Output is correct
17	Correct	665 ms	48696 KB	Output is correct
18	Correct	47 ms	12020 KB	Output is correct
19	Correct	257 ms	29492 KB	Output is correct
20	Correct	676 ms	48920 KB	Output is correct
21	Correct	404 ms	36496 KB	Output is correct
22	Correct	228 ms	29828 KB	Output is correct
23	Correct	684 ms	48904 KB	Output is correct
24	Correct	651 ms	49220 KB	Output is correct
25	Correct	646 ms	48764 KB	Output is correct
26	Correct	244 ms	28780 KB	Output is correct
27	Correct	236 ms	28832 KB	Output is correct
28	Correct	240 ms	28704 KB	Output is correct
29	Correct	236 ms	28828 KB	Output is correct
30	Correct	249 ms	29004 KB	Output is correct
31	Correct	8 ms	7416 KB	Output is correct
32	Correct	8 ms	7416 KB	Output is correct
33	Correct	8 ms	7416 KB	Output is correct
34	Correct	8 ms	7416 KB	Output is correct
35	Correct	8 ms	7340 KB	Output is correct
36	Correct	8 ms	7416 KB	Output is correct
37	Correct	8 ms	7416 KB	Output is correct
38	Correct	8 ms	7372 KB	Output is correct
39	Correct	8 ms	7416 KB	Output is correct
40	Correct	8 ms	7432 KB	Output is correct
41	Correct	339 ms	35172 KB	Output is correct
42	Correct	685 ms	47712 KB	Output is correct
43	Correct	624 ms	47804 KB	Output is correct
44	Correct	194 ms	30908 KB	Output is correct
45	Correct	612 ms	47692 KB	Output is correct
46	Correct	590 ms	47704 KB	Output is correct
47	Correct	566 ms	47800 KB	Output is correct
48	Correct	595 ms	47876 KB	Output is correct
49	Correct	584 ms	47692 KB	Output is correct
50	Correct	589 ms	47864 KB	Output is correct
51	Correct	587 ms	47800 KB	Output is correct
52	Correct	591 ms	47680 KB	Output is correct
53	Correct	585 ms	47752 KB	Output is correct
54	Correct	566 ms	47888 KB	Output is correct
55	Correct	593 ms	47900 KB	Output is correct
56	Correct	593 ms	47752 KB	Output is correct
57	Correct	599 ms	47740 KB	Output is correct
58	Correct	604 ms	47708 KB	Output is correct
59	Correct	162 ms	28472 KB	Output is correct
60	Correct	610 ms	47748 KB	Output is correct
61	Correct	532 ms	48416 KB	Output is correct
62	Correct	185 ms	28464 KB	Output is correct
63	Correct	262 ms	42296 KB	Output is correct
64	Correct	182 ms	28560 KB	Output is correct
65	Correct	263 ms	28524 KB	Output is correct
66	Correct	385 ms	43244 KB	Output is correct
67	Correct	258 ms	31032 KB	Output is correct
68	Correct	187 ms	28588 KB	Output is correct
69	Correct	188 ms	31008 KB	Output is correct
70	Correct	192 ms	28572 KB	Output is correct
71	Correct	190 ms	30992 KB	Output is correct
72	Correct	433 ms	35860 KB	Output is correct
73	Correct	659 ms	48224 KB	Output is correct
74	Correct	723 ms	48308 KB	Output is correct
75	Correct	730 ms	48156 KB	Output is correct
76	Correct	639 ms	48116 KB	Output is correct
77	Correct	654 ms	48228 KB	Output is correct
78	Correct	659 ms	48204 KB	Output is correct
79	Correct	644 ms	48164 KB	Output is correct
80	Correct	642 ms	48268 KB	Output is correct
81	Correct	669 ms	48204 KB	Output is correct
82	Correct	652 ms	48196 KB	Output is correct
83	Correct	653 ms	48152 KB	Output is correct
84	Correct	668 ms	48040 KB	Output is correct
85	Correct	664 ms	48196 KB	Output is correct
86	Correct	675 ms	48088 KB	Output is correct
87	Correct	673 ms	48136 KB	Output is correct
88	Correct	684 ms	48112 KB	Output is correct
89	Correct	230 ms	29428 KB	Output is correct
90	Correct	680 ms	48220 KB	Output is correct
91	Correct	623 ms	49596 KB	Output is correct
92	Correct	235 ms	29584 KB	Output is correct
93	Correct	373 ms	43812 KB	Output is correct
94	Correct	237 ms	29580 KB	Output is correct
95	Correct	263 ms	29484 KB	Output is correct
96	Correct	443 ms	45328 KB	Output is correct
97	Correct	241 ms	32188 KB	Output is correct
98	Correct	236 ms	29508 KB	Output is correct
99	Correct	271 ms	32196 KB	Output is correct
100	Correct	259 ms	29800 KB	Output is correct

답안 #42500

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 13.0 / 13.0

Subtask #3 12.0 / 12.0

Subtask #4 19.0 / 19.0

Subtask #5 46.0 / 46.0

Subtask #1
10.0 / 10.0

Subtask #2
13.0 / 13.0

Subtask #3
12.0 / 12.0

Subtask #4
19.0 / 19.0

Subtask #5
46.0 / 46.0