oj.uz

Submission #567716

# Submission time Handle Problem Language Result Execution time Memory
567716 2022-05-24T05:43:39 Z hhhhaura Swapping Cities (APIO20_swap) C++14
7 / 100
 698 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 ii = 0, x = X, y = Y;
		int L = max(go(X, l, 1), go(Y, r, 1));
		ii = 0, x = X, y = Y;
		while(ii < 3 && v[x][ii].y == ac[0][x]) ii++;
		if(v[x][ii].y != -1) x = v[x][ii].y;
		ii = 0;
		while(ii < 3 && v[y][ii].y == ac[0][y]) ii++;
		if(v[y][ii].y != -1) y = v[y][ii].y;
		int R = min(go(x, dep[x] - dep[lca] - 1, 0), 
			go(y, dep[y] - dep[lca] - 1, 0));
		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);
		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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 94 ms 34280 KB Output is correct
10 Correct 108 ms 44500 KB Output is correct
11 Correct 108 ms 42808 KB Output is correct
12 Correct 134 ms 46060 KB Output is correct
13 Correct 117 ms 49444 KB Output is correct
14 Correct 114 ms 33024 KB Output is correct
15 Correct 502 ms 45620 KB Output is correct
16 Correct 494 ms 41356 KB Output is correct
17 Correct 442 ms 50916 KB Output is correct
18 Correct 512 ms 48064 KB Output is correct
19 Runtime error 698 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 309 ms 36456 KB Output is correct
4 Correct 261 ms 39872 KB Output is correct
5 Correct 267 ms 38724 KB Output is correct
6 Correct 258 ms 39752 KB Output is correct
7 Correct 269 ms 39268 KB Output is correct
8 Correct 277 ms 37804 KB Output is correct
9 Correct 261 ms 39104 KB Output is correct
10 Correct 275 ms 37552 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Runtime error 526 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 526 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 94 ms 34280 KB Output is correct
10 Correct 108 ms 44500 KB Output is correct
11 Correct 108 ms 42808 KB Output is correct
12 Correct 134 ms 46060 KB Output is correct
13 Correct 117 ms 49444 KB Output is correct
14 Correct 114 ms 33024 KB Output is correct
15 Correct 502 ms 45620 KB Output is correct
16 Correct 494 ms 41356 KB Output is correct
17 Correct 442 ms 50916 KB Output is correct
18 Correct 512 ms 48064 KB Output is correct
19 Correct 309 ms 36456 KB Output is correct
20 Correct 261 ms 39872 KB Output is correct
21 Correct 267 ms 38724 KB Output is correct
22 Correct 258 ms 39752 KB Output is correct
23 Correct 269 ms 39268 KB Output is correct
24 Correct 277 ms 37804 KB Output is correct
25 Correct 261 ms 39104 KB Output is correct
26 Correct 275 ms 37552 KB Output is correct
27 Correct 1 ms 584 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 432 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Incorrect 2 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 526 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -