답안 #88653 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88653	2018-12-07T09:03:09 Z	dimash241	Evacuation plan (IZhO18_plan)	C++17	100 / 100	854 ms	72476 KB

plan

# include <stdio.h>
# include <bits/stdc++.h>


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;

inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 1e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
bool u[N];
int tin[N], tout[N], timer;
vector < pair < int, int > > g[N], gr[N];
vector < pair < int, pair < int, int > > > all;
int d[N], mx[N][22], pr[N][22];
int p[N], sz[N];

int get (int a) {
	if (a == p[a]) return a;
	return p[a] = get(p[a]);
}

bool uni (int a, int b) {
	a = get(a), b = get(b);

	if (a == b) return 0;
	if (sz[a] > sz[b]) swap(a, b);
	sz[b] += sz[a];
	p[a] = b;
	return 1;
}

void dfs (int v) {
	u[v] = 1;
	tin[v] = ++ timer;
	For (i, 1, 18) {
		pr[v][i] = pr[pr[v][i - 1]][i - 1];
		mx[v][i] = min(mx[v][i - 1], mx[pr[v][i - 1]][i - 1]);
	}

	for (auto to : gr[v]) {
		if (!u[to.F]) {
			mx[to.F][0] = to.S;
			pr[to.F][0] = v;
			dfs (to.F);            
		}
	}

	tout[v] = timer;
}

bool upper (int a, int b) {
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca (int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;

	for (int i = 18; i >= 0; i --) {
		if (!upper(pr[a][i], b))
			a = pr[a][i];
	}

	return pr[a][0];
}

int get (int a, int b) {
	int res = inf;
	if (a == b) return res;

	for (int i = 18; i >= 0; i --) {
		if (!upper(pr[a][i], b)) {
			res = min(res, mx[a][i]);
			a = pr[a][i];
		}
	}

	return min(res, mx[a][0]);
}


int main () {
	SpeedForce;
	// freopen("out", "w", stdout);               
	cin >> n >> m;
	tout[0] = inf;
	For (i, 1, m) {
		int l, r, x;
		cin >> l >> r >> x;
		g[l].pb(mp(r, x));
		g[r].pb(mp(l, x));
		all.pb(mp(x, mp(l, r)));
	}

	set < pair < int, int > > s;

	cin >> k;
	for (int i = 1; i <= n; i ++) {
		d[i] = inf;
		p[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= k; i ++) {
		int x;
		cin >> x;
		s.insert(mp(0, x));
		d[x] = 0;
	}

	while (s.size()) {
		int v = s.begin() -> S;
		s.erase(s.begin());

		for (auto to : g[v]) {
			if (d[to.F] > d[v] + to.S) {
				s.erase(mp(d[to.F], to.F));
				d[to.F] = d[v] + to.S;
				s.insert(mp(d[to.F], to.F));
			}
		}
	}
	for (auto &it : all) {
		
		it.F = min(d[it.S.F], d[it.S.S]);
	}
	sort(every(all));
	reverse(every(all));

	for (auto it : all) {
		if (uni(it.S.F, it.S.S)) {
			gr[it.S.F].pb(mp(it.S.S, it.F));
			gr[it.S.S].pb(mp(it.S.F, it.F));
		//	cout << it.S.F << ' ' << it.S.S << ' ' <<  << '\n';
		}
	}       

	dfs (1);

	int q;
	cin >> q;
	while (q -- ) {
		int l, r;
		cin >> l >> r;

		int x = lca(l, r);
	//	cout << x << ' ' << l << ' ' << r << " query " << get(l, x) << ' ' << get(r, x) << ' ' ;

		cout << min(get(l, x), get(r, x)) << '\n';
	}

    return Accepted;
}

// Coded By OB

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	28536 KB	Output is correct
2	Correct	30 ms	28920 KB	Output is correct
3	Correct	29 ms	28920 KB	Output is correct
4	Correct	27 ms	28536 KB	Output is correct
5	Correct	29 ms	28920 KB	Output is correct
6	Correct	29 ms	28792 KB	Output is correct
7	Correct	27 ms	28536 KB	Output is correct
8	Correct	27 ms	28664 KB	Output is correct
9	Correct	29 ms	28912 KB	Output is correct
10	Correct	29 ms	28920 KB	Output is correct
11	Correct	29 ms	28920 KB	Output is correct
12	Correct	29 ms	28920 KB	Output is correct
13	Correct	29 ms	28920 KB	Output is correct
14	Correct	29 ms	28792 KB	Output is correct
15	Correct	29 ms	28924 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	28536 KB	Output is correct
2	Correct	30 ms	28920 KB	Output is correct
3	Correct	29 ms	28920 KB	Output is correct
4	Correct	27 ms	28536 KB	Output is correct
5	Correct	29 ms	28920 KB	Output is correct
6	Correct	29 ms	28792 KB	Output is correct
7	Correct	27 ms	28536 KB	Output is correct
8	Correct	27 ms	28664 KB	Output is correct
9	Correct	29 ms	28912 KB	Output is correct
10	Correct	29 ms	28920 KB	Output is correct
11	Correct	29 ms	28920 KB	Output is correct
12	Correct	29 ms	28920 KB	Output is correct
13	Correct	29 ms	28920 KB	Output is correct
14	Correct	29 ms	28792 KB	Output is correct
15	Correct	29 ms	28924 KB	Output is correct
16	Correct	291 ms	51400 KB	Output is correct
17	Correct	836 ms	70452 KB	Output is correct
18	Correct	79 ms	33456 KB	Output is correct
19	Correct	242 ms	58396 KB	Output is correct
20	Correct	785 ms	71192 KB	Output is correct
21	Correct	439 ms	60368 KB	Output is correct
22	Correct	255 ms	61228 KB	Output is correct
23	Correct	833 ms	71300 KB	Output is correct
24	Correct	841 ms	71340 KB	Output is correct
25	Correct	822 ms	71184 KB	Output is correct
26	Correct	249 ms	58248 KB	Output is correct
27	Correct	249 ms	58240 KB	Output is correct
28	Correct	247 ms	58140 KB	Output is correct
29	Correct	244 ms	58272 KB	Output is correct
30	Correct	259 ms	58320 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	28536 KB	Output is correct
2	Correct	27 ms	28540 KB	Output is correct
3	Correct	27 ms	28536 KB	Output is correct
4	Correct	28 ms	28636 KB	Output is correct
5	Correct	26 ms	28540 KB	Output is correct
6	Correct	27 ms	28536 KB	Output is correct
7	Correct	26 ms	28536 KB	Output is correct
8	Correct	27 ms	28632 KB	Output is correct
9	Correct	26 ms	28636 KB	Output is correct
10	Correct	26 ms	28636 KB	Output is correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	392 ms	59568 KB	Output is correct
2	Correct	728 ms	70040 KB	Output is correct
3	Correct	730 ms	70040 KB	Output is correct
4	Correct	194 ms	58152 KB	Output is correct
5	Correct	723 ms	70120 KB	Output is correct
6	Correct	703 ms	70044 KB	Output is correct
7	Correct	717 ms	69948 KB	Output is correct
8	Correct	718 ms	70008 KB	Output is correct
9	Correct	733 ms	69992 KB	Output is correct
10	Correct	740 ms	69988 KB	Output is correct
11	Correct	723 ms	70112 KB	Output is correct
12	Correct	747 ms	70244 KB	Output is correct
13	Correct	726 ms	70180 KB	Output is correct
14	Correct	723 ms	70120 KB	Output is correct
15	Correct	743 ms	70232 KB	Output is correct
16	Correct	736 ms	70096 KB	Output is correct
17	Correct	719 ms	70132 KB	Output is correct
18	Correct	707 ms	70136 KB	Output is correct
19	Correct	190 ms	59880 KB	Output is correct
20	Correct	707 ms	70076 KB	Output is correct
21	Correct	656 ms	70736 KB	Output is correct
22	Correct	192 ms	57800 KB	Output is correct
23	Correct	205 ms	56920 KB	Output is correct
24	Correct	187 ms	57744 KB	Output is correct
25	Correct	193 ms	57744 KB	Output is correct
26	Correct	222 ms	57256 KB	Output is correct
27	Correct	205 ms	59700 KB	Output is correct
28	Correct	192 ms	57816 KB	Output is correct
29	Correct	203 ms	59048 KB	Output is correct
30	Correct	190 ms	57752 KB	Output is correct
31	Correct	240 ms	58980 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	28536 KB	Output is correct
2	Correct	30 ms	28920 KB	Output is correct
3	Correct	29 ms	28920 KB	Output is correct
4	Correct	27 ms	28536 KB	Output is correct
5	Correct	29 ms	28920 KB	Output is correct
6	Correct	29 ms	28792 KB	Output is correct
7	Correct	27 ms	28536 KB	Output is correct
8	Correct	27 ms	28664 KB	Output is correct
9	Correct	29 ms	28912 KB	Output is correct
10	Correct	29 ms	28920 KB	Output is correct
11	Correct	29 ms	28920 KB	Output is correct
12	Correct	29 ms	28920 KB	Output is correct
13	Correct	29 ms	28920 KB	Output is correct
14	Correct	29 ms	28792 KB	Output is correct
15	Correct	29 ms	28924 KB	Output is correct
16	Correct	291 ms	51400 KB	Output is correct
17	Correct	836 ms	70452 KB	Output is correct
18	Correct	79 ms	33456 KB	Output is correct
19	Correct	242 ms	58396 KB	Output is correct
20	Correct	785 ms	71192 KB	Output is correct
21	Correct	439 ms	60368 KB	Output is correct
22	Correct	255 ms	61228 KB	Output is correct
23	Correct	833 ms	71300 KB	Output is correct
24	Correct	841 ms	71340 KB	Output is correct
25	Correct	822 ms	71184 KB	Output is correct
26	Correct	249 ms	58248 KB	Output is correct
27	Correct	249 ms	58240 KB	Output is correct
28	Correct	247 ms	58140 KB	Output is correct
29	Correct	244 ms	58272 KB	Output is correct
30	Correct	259 ms	58320 KB	Output is correct
31	Correct	27 ms	28536 KB	Output is correct
32	Correct	27 ms	28540 KB	Output is correct
33	Correct	27 ms	28536 KB	Output is correct
34	Correct	28 ms	28636 KB	Output is correct
35	Correct	26 ms	28540 KB	Output is correct
36	Correct	27 ms	28536 KB	Output is correct
37	Correct	26 ms	28536 KB	Output is correct
38	Correct	27 ms	28632 KB	Output is correct
39	Correct	26 ms	28636 KB	Output is correct
40	Correct	26 ms	28636 KB	Output is correct
41	Correct	392 ms	59568 KB	Output is correct
42	Correct	728 ms	70040 KB	Output is correct
43	Correct	730 ms	70040 KB	Output is correct
44	Correct	194 ms	58152 KB	Output is correct
45	Correct	723 ms	70120 KB	Output is correct
46	Correct	703 ms	70044 KB	Output is correct
47	Correct	717 ms	69948 KB	Output is correct
48	Correct	718 ms	70008 KB	Output is correct
49	Correct	733 ms	69992 KB	Output is correct
50	Correct	740 ms	69988 KB	Output is correct
51	Correct	723 ms	70112 KB	Output is correct
52	Correct	747 ms	70244 KB	Output is correct
53	Correct	726 ms	70180 KB	Output is correct
54	Correct	723 ms	70120 KB	Output is correct
55	Correct	743 ms	70232 KB	Output is correct
56	Correct	736 ms	70096 KB	Output is correct
57	Correct	719 ms	70132 KB	Output is correct
58	Correct	707 ms	70136 KB	Output is correct
59	Correct	190 ms	59880 KB	Output is correct
60	Correct	707 ms	70076 KB	Output is correct
61	Correct	656 ms	70736 KB	Output is correct
62	Correct	192 ms	57800 KB	Output is correct
63	Correct	205 ms	56920 KB	Output is correct
64	Correct	187 ms	57744 KB	Output is correct
65	Correct	193 ms	57744 KB	Output is correct
66	Correct	222 ms	57256 KB	Output is correct
67	Correct	205 ms	59700 KB	Output is correct
68	Correct	192 ms	57816 KB	Output is correct
69	Correct	203 ms	59048 KB	Output is correct
70	Correct	190 ms	57752 KB	Output is correct
71	Correct	240 ms	58980 KB	Output is correct
72	Correct	470 ms	61296 KB	Output is correct
73	Correct	846 ms	71968 KB	Output is correct
74	Correct	824 ms	71884 KB	Output is correct
75	Correct	818 ms	72004 KB	Output is correct
76	Correct	820 ms	71524 KB	Output is correct
77	Correct	854 ms	71780 KB	Output is correct
78	Correct	814 ms	71836 KB	Output is correct
79	Correct	827 ms	71844 KB	Output is correct
80	Correct	837 ms	71712 KB	Output is correct
81	Correct	854 ms	72000 KB	Output is correct
82	Correct	839 ms	71576 KB	Output is correct
83	Correct	821 ms	71628 KB	Output is correct
84	Correct	851 ms	71832 KB	Output is correct
85	Correct	832 ms	70780 KB	Output is correct
86	Correct	839 ms	70676 KB	Output is correct
87	Correct	840 ms	70736 KB	Output is correct
88	Correct	828 ms	71904 KB	Output is correct
89	Correct	326 ms	60872 KB	Output is correct
90	Correct	840 ms	72188 KB	Output is correct
91	Correct	758 ms	72476 KB	Output is correct
92	Correct	275 ms	58780 KB	Output is correct
93	Correct	321 ms	58544 KB	Output is correct
94	Correct	277 ms	58960 KB	Output is correct
95	Correct	270 ms	59164 KB	Output is correct
96	Correct	337 ms	58280 KB	Output is correct
97	Correct	345 ms	59932 KB	Output is correct
98	Correct	276 ms	59192 KB	Output is correct
99	Correct	326 ms	61292 KB	Output is correct
100	Correct	274 ms	58832 KB	Output is correct

답안 #88653

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