Submission #410209

#	Time	Username	Problem	Language	Result	Execution time	Memory
410209		CSQ31	Swapping Cities (APIO20_swap)	C++14	100 / 100	622 ms	93732 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
const int MAXN = 3e5+5;
vii adj(MAXN);
int cnt = 0;
vector<int>p(MAXN),deg(MAXN),ans(MAXN,2e9);
vector<bool>can(MAXN);
vii mn(20,vector<int>(MAXN,2e9)),par(20,vector<int>(MAXN,0));
int find(int x){
	if(p[x] == x)return x;
	else return p[x] = find(p[x]);
}
bool unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return 0;
	p[a] = p[b] = cnt;
	can[cnt] = can[a] | can[b];
	
	adj[cnt].pb(a);
	adj[cnt].pb(b);
	cnt++;
	return 1;
}
ll tin[MAXN],tout[MAXN],depth[MAXN];
int timer = 0;
void euler(int v,int u){
	tin[v] = timer++;
	for(int x:adj[v]){
		if(x == u)continue;
		euler(x,v);
	}
	tout[v] = timer;
}
void dfs(int v,int u){
	tin[v] = timer++;
	if(can[v])mn[0][v] = ans[v];
	for(int x:adj[v]){
	    if(x == u)continue;	
	    par[0][x] = v;
	   if(can[x]) mn[0][x] = ans[x];
	   if(can[v]) mn[0][x] = min(mn[0][x],ans[v]);
	    depth[x] = depth[v]+1;
	    for(int i=1;i<=19;i++){
			par[i][x] = par[i-1][par[i-1][x]];
			mn[i][x] = min(mn[i-1][x],mn[i-1][par[i-1][x]]);
		}
		dfs(x,v);
	}
	tout[v] = timer;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
	if(depth[v] > depth[u])swap(u,v);
	int dist = depth[u]-depth[v];
	for(int i=0;dist;i++,dist>>=1){
		if(dist&1)u = par[i][u];
	}
	if(u == v)return u;
	for(int i=19;i>=0;i--){
		if(par[i][v] != par[i][u]){
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}	
void init(int n, int m,vector<int> u,vector<int> v,vector<int> w) {
	vector<pair<int,pii>>e;
	cnt=n+1;
	for(int i=1;i<=n+m;i++)p[i] = i;
	for(int i=0;i<m;i++)e.pb({w[i],{u[i]+1,v[i]+1}});
	sort(all(e));
	for(auto z : e){
		int ww = z.fi;
		pii v = z.se;
		ans[cnt] = ww;
		if(!unite(v.fi,v.se)){
			adj[cnt].pb(find(v.fi));
			p[find(v.fi)] = cnt;
			can[cnt] = 1;
			cnt++;
		}
		else{
			deg[v.fi]++;
			deg[v.se]++;
			if(deg[v.fi]>=3 || deg[v.se]>=3)can[find(v.fi)] = 1;
		}
	}
	dfs(cnt-1,-1);
}

int getMinimumFuelCapacity(int x, int y) {
	int v = lca(x+1,y+1);
	int a = mn[0][v];
	//cout<<v<<'\n';
	for(int i=19;i>=0;i--){
		if(par[i][v]){
			a = min(a,mn[i][v]);
			v = par[i][v];
		}
	}
	if(a == 2e9)a=-1;
	return a;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27