제출 #567678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567678		hhhhaura	자매 도시 (APIO20_swap)	C++14	0 / 100	703 ms	524288 KiB

swap

#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);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27