Submission #406299

#	Time	Username	Problem	Language	Result	Execution time	Memory
406299		amunduzbaev	Swapping Cities (APIO20_swap)	C++14	Compilation error	0 ms	0 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
#include "grader.cpp"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define int long long
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int N = 3e5+5;
const int mod = 1e9+7;

int n, m, par[N], d[N], f[N], w[N];
vector<int> edges[N];
int lca[N][30], tin[N], tout[N], t;

int fx(int x) { return (x == par[x] ? x : par[x] = fx(par[x])); }
void merge(int a, int b, int c){
	d[a]++, d[b]++;
	int cnd = (max(d[a], d[b]) >= 3);
	a = fx(a), b = fx(b);
	edges[n].pb(a);
	if(b != a) edges[n].pb(b);
	if(a == b){
		par[a] = par[b] = n;
		par[n] = n, f[n] = 1, w[n] = c;
	} else {
		par[a] = par[b] = n, w[n] = c;
		par[n] = n, f[n] = f[a] | f[b] | cnd;
	} n++;
}

void dfs(int u, int p){
	tin[u] = t++;
	lca[u][0] = p;
	for(int j=1;j<30;j++) lca[u][j] = lca[lca[u][j-1]][j-1];
	for(auto x : edges[u]) dfs(x, u);
	tout[u] = t - 1;
}

void init(int32_t N, int32_t M,
	vector<int32_t> a, vector<int32_t> b, vector<int32_t> c) {
	n = N, m = M;
	vector<array<int, 3>> tt;
	for(int i=0;i<m;i++) tt.pb({c[i], a[i], b[i]});
	sort(tt.begin(), tt.end());
	for(int i=0;i<n;i++) par[i] = i;
	for(auto x : tt) merge(x[1], x[2], x[0]);
	//for(int i=n-1;i>=0;i--){
		//for(auto x : edges[i]) cout<<x<<" "<<i<<"\n";
	//}
	memset(lca, -1, sizeof lca);
	dfs(n-1, n-1);
}

bool up(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int f_lca(int a, int b){
	if(up(b, a)) return b;
	if(up(a, b)) return a;
	for(int i=29;i>=0;i--){
		if(up(lca[a][i], b)) continue;
		a = lca[a][i];
	} return lca[a][0];
}

/*

5 4
0 1 0
1 2 1
2 3 2
3 4 3
5
0 1
1 2
2 3
3 4
0 4

*/

int32_t getMinimumFuelCapacity(int32_t x, int32_t y) {
	int lc = f_lca(x, y);
	if(f[lc]) return w[lc];
	for(int i=29;i>=0;i--){
		if(f[lca[lc][i]]) continue;
		lc = lca[lc][i];
	} 
	if(f[lca[lc][0]]) return w[lca[lc][0]];
	else return -1;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccQoBmfH.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc7iLOLJ.o:swap.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status