oj.uz

Submission #567717

# Submission time Handle Problem Language Result Execution time Memory
567717 2022-05-24T05:45:44 Z hhhhaura Swapping Cities (APIO20_swap) C++14
7 / 100
 692 ms 524288 KB 
#define wiwihorz
#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ll long long int
#define pii pair<int, int>
#define INF 2000000000
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
vector<vector<int>> ac, mx, mn;
vector<vector<pii>> v, mp;
vector<int> dep;
int lg;
void dfs(int x, int par, int d, int es, int val) {
	ac[0][x] = par;
	mx[0][x] = es;
	mn[0][x] = val;
	dep[x] = d;
	vector<pii> tp;
	for(auto i : mp[x]) tp.push_back({i.y, i.x});
	sort(all(tp));
	rep(i, 0, min(signed(tp.size()), 3) - 1) v[x][i] = tp[i];
	for(auto i : mp[x]) if(i.x != par) {
		int ii = 0;
		while(ii < 3 && (v[x][ii].y == i.x || v[x][ii].y == par)) ii++;
		dfs(i.x, x, d + 1, i.y, v[x][ii].x);
	}
}
int LCA(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	int need = dep[a] - dep[b];
	rep(i, 0, lg) if((need >> i) & 1) {
		a = ac[i][a];
	} 
	if(a == b) return a;
	rrep(i, 0, lg) if(ac[i][a] != ac[i][b]) {
		a = ac[i][a];
		b = ac[i][b];
	}
	return ac[0][a];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	lg = 31 - __builtin_clz(N);
	mp.assign(N, vector<pii>());
	ac.assign(lg + 1, vector<int>(N, 0));
	mx.assign(lg + 1, vector<int>(N, 0));
	mn.assign(lg + 1, vector<int>(N, INF));
	v.assign(N, vector<pii>(3, {INF, -1}));
	dep.assign(N, 0);
	rep(i, 0, M - 1) {
		mp[U[i]].push_back({V[i], W[i]});
		mp[V[i]].push_back({U[i], W[i]});
	}
	dfs(0, 0, 0, 0, INF);
	rep(i, 1, lg) rep(j, 0, N - 1) {
		ac[i][j] = ac[i - 1][ac[i - 1][j]];
		mx[i][j] = max(mx[i - 1][j], mx[i - 1][ac[i - 1][j]]);
		mn[i][j] = min(mn[i - 1][j], mn[i - 1][ac[i - 1][j]]);
	}
	return;
}
int go(int a, int x, int tp) {
	if(tp == 1) {
		int ans = 0;
		if(x > 0) rep(i, 0, lg) if((x >> i) & 1) {
			ans = max(ans, mx[i][a]);
			a = ac[i][a];
		}
		return ans;
	}
	else {
		int ans = INF;
		if(x > 0) rep(i, 0, lg) if((x >> i) & 1) {
			ans = min(ans, mn[i][a]);
			a = ac[i][a];
		}
		return ans;
	}
}
int getMinimumFuelCapacity(int X, int Y) {	
	if(dep[X] < dep[Y]) swap(X, Y);
	int lca = LCA(X, Y);
	auto get_sec = [&](int x, int no) {
		int a = INF, b = INF;
		rep(i, 0, 2) if(v[x][i].y != no) {
			int cur = v[x][i].x;
			if(cur < a) swap(cur, a);
			if(cur < b) swap(cur, b);
		}
		return b;
	};
	if(lca == Y) {
		int need = dep[X] - dep[Y];
		int L = go(X, need, 1);
		int R = go(X, need - 1, 0);
		int to = X;
		need --;
		rep(i, 0, lg) if((need >> i) & 1) to = ac[i][to];
		R = min({R, get_sec(X, ac[0][X]), get_sec(Y, to)});
		return max(L, R) == INF ? -1 : max(L, R);
	}
	else {
		int l = dep[X] - dep[lca];
		int r = dep[Y] - dep[lca];
		int L = max(go(X, l, 1), go(Y, r, 1));
		int R = min(go(X, l - 1, 0), go(Y, r - 1, 0));
		int ii = 0, x = X, y = Y;
		rep(i, 0, lg) if(((l - 1) >> i) & 1) x = ac[i][x];
		rep(i, 0, lg) if(((r - 1) >> i) & 1) y = ac[i][y];
		while(ii < 3 && (v[lca][ii].y == x || v[lca][ii].y == y)) ii ++;
		R = min({R, v[lca][ii].x, get_sec(X, ac[0][X]), get_sec(Y, ac[0][Y])});
		return max(L, R) == INF ? -1 : max(L, R);
	}
}

Compilation message

swap.cpp:6: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    6 | #pragma loop-opt(on)
      | 
swap.cpp:16:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
swap.cpp:16:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 103 ms 34576 KB Output is correct
10 Correct 136 ms 44972 KB Output is correct
11 Correct 110 ms 43372 KB Output is correct
12 Correct 134 ms 46500 KB Output is correct
13 Correct 137 ms 50064 KB Output is correct
14 Correct 125 ms 33436 KB Output is correct
15 Correct 528 ms 46552 KB Output is correct
16 Correct 564 ms 42048 KB Output is correct
17 Correct 484 ms 51656 KB Output is correct
18 Correct 535 ms 48912 KB Output is correct
19 Runtime error 692 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 270 ms 36436 KB Output is correct
4 Correct 246 ms 37952 KB Output is correct
5 Correct 274 ms 36836 KB Output is correct
6 Correct 285 ms 37820 KB Output is correct
7 Correct 275 ms 37336 KB Output is correct
8 Correct 279 ms 35952 KB Output is correct
9 Correct 252 ms 37212 KB Output is correct
10 Correct 267 ms 35672 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Runtime error 546 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 546 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 103 ms 34576 KB Output is correct
10 Correct 136 ms 44972 KB Output is correct
11 Correct 110 ms 43372 KB Output is correct
12 Correct 134 ms 46500 KB Output is correct
13 Correct 137 ms 50064 KB Output is correct
14 Correct 125 ms 33436 KB Output is correct
15 Correct 528 ms 46552 KB Output is correct
16 Correct 564 ms 42048 KB Output is correct
17 Correct 484 ms 51656 KB Output is correct
18 Correct 535 ms 48912 KB Output is correct
19 Correct 270 ms 36436 KB Output is correct
20 Correct 246 ms 37952 KB Output is correct
21 Correct 274 ms 36836 KB Output is correct
22 Correct 285 ms 37820 KB Output is correct
23 Correct 275 ms 37336 KB Output is correct
24 Correct 279 ms 35952 KB Output is correct
25 Correct 252 ms 37212 KB Output is correct
26 Correct 267 ms 35672 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Incorrect 1 ms 596 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 546 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -