Submission #292943

#	Time	Username	Problem	Language	Result	Execution time	Memory
292943		arnold518	Swapping Cities (APIO20_swap)	C++14	100 / 100	765 ms	59632 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 2e5;

struct Edge
{
	int u, v, w;
};

int N, M;
vector<pii> adj[MAXN+10];
Edge E[MAXM+10];

int deg[MAXN+10];
int par[MAXN+10], maxd[MAXN+10], sz[MAXN+10], ecnt[MAXN+10];
vector<pii> adj2[MAXN+10];
int T[MAXN+10];

int Find(int x)
{
	if(x==par[x]) return x;
	return Find(par[x]);
}

vector<int> V[MAXN+10];

void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x, y);
	for(auto it : V[x]) V[y].push_back(it);
	V[x].clear();
	par[x]=y;
	maxd[y]=max(maxd[y], maxd[x]);
	sz[y]+=sz[x];
	ecnt[y]+=ecnt[x];
}

int ppar[MAXN+10][30], dep[MAXN+10], spa[MAXN+10][30];

void dfs(int now, int bef, int d, int val)
{
	dep[now]=d;
	ppar[now][0]=bef;
	spa[now][0]=val;
	for(auto nxt : adj2[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, d+1, nxt.second);
	}
}

int maxdist(int u, int v)
{
	int ans=0;
	if(dep[u]>dep[v]) swap(u, v);
	for(int i=20; i>=0; i--) if(dep[ppar[v][i]]>=dep[u])
	{
		ans=max(ans, spa[v][i]);
		v=ppar[v][i];
	}
	if(u==v) return ans;
	for(int i=20; i>=0; i--) if(ppar[u][i]!=ppar[v][i])
	{
		ans=max(ans, spa[u][i]);
		ans=max(ans, spa[v][i]);
		u=ppar[u][i]; v=ppar[v][i];
	}
	ans=max(ans, spa[u][0]);
	ans=max(ans, spa[v][0]);
	return ans;
}


void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W)
{
	N=_N; M=_M; 
	for(int i=0; i<M; i++)
	{
		int u=_U[i]+1, v=_V[i]+1, w=_W[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		E[i+1]={u, v, w};
	}

	sort(E+1, E+M+1, [&](const Edge &p, const Edge &q) { return p.w<q.w; });

	for(int i=1; i<=N; i++)
	{
		deg[i]=0;
		maxd[i]=0;
		par[i]=i;
		sz[i]=1; ecnt[i]=0;
		T[i]=1e9;
		V[i].push_back(i);
	}

	for(int i=1; i<=M; i++)
	{
		int u=E[i].u, v=E[i].v, w=E[i].w;
		deg[u]++; deg[v]++;
		if(Find(u)!=Find(v))
		{
			//printf("%d %d %d\n", u, v, w);
			adj2[u].push_back({v, w});
			adj2[v].push_back({u, w});
			Union(u, v);
		}

		ecnt[Find(u)]++;
		maxd[Find(u)]=max(maxd[Find(u)], max(deg[u], deg[v]));

		if(maxd[Find(u)]>=3 || (maxd[Find(u)]==2 && ecnt[Find(u)]==sz[Find(u)]))
		{
			for(auto it : V[Find(u)]) T[it]=E[i].w;
			V[Find(u)].clear();
		}
		//if(Find(X)==Find(Y) && maxd[Find(X)]==2 && ecnt[Find(X)]==sz[Find(X)]) { ans=E[i].w; break; }
	}
	dfs(1, 1, 1, 0);

	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++)
	{
		ppar[j][i]=ppar[ppar[j][i-1]][i-1];
		spa[j][i]=max(spa[j][i-1], spa[ppar[j][i-1]][i-1]);
	}

	//for(int i=1; i<=N; i++) printf("T %d : %d\n", i, T[i]);
}

int X, Y;

int getMinimumFuelCapacity(int _X, int _Y)
{
	X=_X+1; Y=_Y+1;

	int ans=maxdist(X, Y);
	ans=max(ans, T[X]);
	ans=max(ans, T[Y]);
	if(ans>=1e9) ans=-1;
	return ans;
}

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