oj.uz

Submission #567678

# Submission time Handle Problem Language Result Execution time Memory
567678 2022-05-24T03:35:42 Z hhhhaura Swapping Cities (APIO20_swap) C++14
0 / 100
 703 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++;
		assert(ii < 3);
		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);
	if(lca == Y) {
		int need = dep[X] - dep[Y];
		int L = go(X, need, 1);
		int R = go(X, need - 1, 0);
		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);
		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 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 692 KB Output is correct
9 Correct 83 ms 34320 KB Output is correct
10 Correct 111 ms 44712 KB Output is correct
11 Correct 104 ms 43064 KB Output is correct
12 Correct 113 ms 46000 KB Output is correct
13 Correct 115 ms 49652 KB Output is correct
14 Correct 116 ms 33056 KB Output is correct
15 Correct 396 ms 45960 KB Output is correct
16 Correct 404 ms 41564 KB Output is correct
17 Correct 345 ms 51148 KB Output is correct
18 Correct 404 ms 48344 KB Output is correct
19 Runtime error 703 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 208 ms 36124 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 692 KB Output is correct
9 Runtime error 547 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 547 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 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 692 KB Output is correct
9 Correct 83 ms 34320 KB Output is correct
10 Correct 111 ms 44712 KB Output is correct
11 Correct 104 ms 43064 KB Output is correct
12 Correct 113 ms 46000 KB Output is correct
13 Correct 115 ms 49652 KB Output is correct
14 Correct 116 ms 33056 KB Output is correct
15 Correct 396 ms 45960 KB Output is correct
16 Correct 404 ms 41564 KB Output is correct
17 Correct 345 ms 51148 KB Output is correct
18 Correct 404 ms 48344 KB Output is correct
19 Incorrect 208 ms 36124 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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