Submission #567758

#	Time	Username	Problem	Language	Result	Execution time	Memory
567758		hhhhaura	Swapping Cities (APIO20_swap)	C++14	100 / 100	403 ms	39180 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
int lg, n, ii, m;
vector<int> dep, par, rk, yes, ord, id, tag, deg;
vector<vector<int>> ac, mp;
int pos(int x) {
	if(par[par[x]] == par[x]) return par[x];
	else return par[x] = pos(par[x]);
}
void unite(int a, int b, int c) {
	int aa = pos(a), bb = pos(b);
	if(aa == bb) return;
	if(rk[aa] < rk[bb]) swap(aa, bb);
	rk[aa] += (rk[aa] == rk[bb]);
	par[bb] = aa;
	yes[aa] |= yes[bb];
	id[aa] = c;
}
void build() {
	ii = n - 1;
	lg = 31 - __builtin_clz(n * 2);
	mp.assign(n * 2, vector<int>());
	ac.assign(lg + 1, vector<int>(n * 2, 0));
	dep.assign(n * 2, 0);
	id.assign(n, 0), iota(all(id), 0);
	par.assign(n, 0), iota(all(par), 0);
	rk.assign(n, 0);
	yes.assign(n, 0);
	ord.assign(m, 0), iota(all(ord), 0);
	tag.assign(n * 2, -1);
	deg.assign(n, 0);
}
void dfs(int x, int par, int d) {
	dep[x] = d;
	ac[0][x] = par;
	for(auto i : mp[x]) if(i != par) {
		dfs(i, x, d + 1);
	}
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	build();
	sort(all(ord), [&](int a, int b) {
		return W[a] < W[b];
	});
	for(auto i : ord) {
		int a = U[i], b = V[i], c = W[i];
		deg[a] ++;
		deg[b] ++;
		if(pos(a) == pos(b)) {	
			a = pos(a);
			if(!yes[a]) {
				yes[a] = 1;
				tag[id[a]] = c;
			}
		}
		else {
			mp[++ii].push_back(id[pos(a)]);
			mp[ii].push_back(id[pos(b)]);
			unite(a, b, ii);
			if(deg[a] > 2 || deg[b] > 2) yes[pos(a)] = 1;
			if(yes[pos(a)]) tag[ii] = c;
		}
	}
	dfs(ii, ii, 0);
	rep(i, 1, lg) rep(j, 0, ii) {
		ac[i][j] = ac[i - 1][ac[i - 1][j]];
	}
}
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];
}
int getMinimumFuelCapacity(int X, int Y) {	
	int lca = LCA(X, Y);
	if(tag[lca] != -1) return tag[lca];
	rrep(i, 0, lg) {
		int to = ac[i][lca];
		if(tag[to] == -1) lca = to;
	}
	return tag[ac[0][lca]];
}

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