oj.uz

답안 #567677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567677 2022-05-24T03:30:47 Z hhhhaura 자매 도시 (APIO20_swap) C++14
0 / 100
 726 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;
	if(x != par) tp.push_back({es, par});
	for(auto i : mp[x]) if(i.x != par) {
		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) return INF;
		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) return INF;
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 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 1 ms 596 KB Output is correct
9 Correct 96 ms 35828 KB Output is correct
10 Correct 112 ms 46268 KB Output is correct
11 Correct 115 ms 44580 KB Output is correct
12 Correct 118 ms 47708 KB Output is correct
13 Correct 128 ms 51268 KB Output is correct
14 Correct 112 ms 34772 KB Output is correct
15 Correct 397 ms 47524 KB Output is correct
16 Correct 405 ms 43316 KB Output is correct
17 Correct 349 ms 52684 KB Output is correct
18 Correct 395 ms 49928 KB Output is correct
19 Runtime error 726 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Incorrect 204 ms 38056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 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 1 ms 596 KB Output is correct
9 Runtime error 568 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 568 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 304 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 1 ms 596 KB Output is correct
9 Correct 96 ms 35828 KB Output is correct
10 Correct 112 ms 46268 KB Output is correct
11 Correct 115 ms 44580 KB Output is correct
12 Correct 118 ms 47708 KB Output is correct
13 Correct 128 ms 51268 KB Output is correct
14 Correct 112 ms 34772 KB Output is correct
15 Correct 397 ms 47524 KB Output is correct
16 Correct 405 ms 43316 KB Output is correct
17 Correct 349 ms 52684 KB Output is correct
18 Correct 395 ms 49928 KB Output is correct
19 Incorrect 204 ms 38056 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 568 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -