oj.uz

Submission #348066

# Submission time Handle Problem Language Result Execution time Memory
348066 2021-01-14T06:41:12 Z arnold518 Swapping Cities (APIO20_swap) C++14
7 / 100
 288 ms 44616 KB 
#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;

int N, M;

struct Edge
{
	int u, v, w;
};
Edge E[MAXM+10];

vector<int> V[MAXN+10];
int deg[MAXN+10], val[MAXN+10], cnt[MAXN+10], sz[MAXN+10];
int ans[MAXN+10];

vector<pii> adj[MAXN+10];

struct UF
{
	int par[MAXN+10];

	void init()
	{
		for(int i=1; i<=N; i++)
		{
			par[i]=i;
		}		
	}

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

int par[MAXN+10][30], len[MAXN+10][30], dep[MAXN+10];
void dfs(int now, int bef, int d)
{
	par[now][0]=bef;
	dep[now]=d;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		len[nxt.first][0]=nxt.second;
		dfs(nxt.first, now, d+1);
	}
}

int lca(int u, int v)
{
	if(dep[u]>dep[v]) swap(u, v);
	int ans=0;
	for(int i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u])
	{
		ans=max(ans, len[v][i]);
		v=par[v][i];
	}
	if(u==v) return ans;
	for(int i=20; i>=0; i--) if(par[u][i]!=par[v][i])
	{
		ans=max(ans, len[v][i]);
		ans=max(ans, len[u][i]);
		u=par[u][i]; v=par[v][i];
	}
	ans=max(ans, len[u][0]);
	ans=max(ans, len[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=1; i<=M; i++)
	{
		int u=_U[i-1]+1, v=_V[i-1]+1, w=_W[i-1];
		E[i]={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++) ans[i]=987654321;
	uf.init();
	for(int i=1; i<=N; i++)
	{
		V[i].push_back(i);
		deg[i]=0;
		val[i]=0;
		cnt[i]=0;
		sz[i]=1;
	}
	for(int i=1; i<=M; i++)
	{
		int u=E[i].u, v=E[i].v, w=E[i].w;
		deg[u]++; deg[v]++;

		int uu=uf.Find(u), vv=uf.Find(v);

		if(uu==vv)
		{
			val[uu]=max(val[uu], deg[u]);
			val[uu]=max(val[uu], deg[v]);
			cnt[uu]++;
		}
		else
		{
			adj[u].push_back({v, w});
			adj[v].push_back({u, w});
			if(V[uu].size()<V[vv].size()) swap(V[uu], V[vv]);
			for(auto it : V[vv]) V[uu].push_back(it);
			V[vv].clear();
			uf.par[vv]=uu;
			val[uu]=max(val[uu], val[vv]);
			cnt[uu]+=cnt[vv];
			sz[uu]+=sz[vv];
			val[uu]=max(val[uu], deg[u]);
			val[uu]=max(val[uu], deg[v]);
			cnt[uu]++;
		}

		bool t=false;
		if(val[uu]>=3) t=true;
		if(val[uu]==2 && cnt[uu]==sz[uu]) t=true;
		if(t)
		{
			for(auto it : V[uu]) ans[it]=w;
			V[uu].clear();
		}
	}

	dfs(1, 0, 1);
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++)
	{
		par[j][i]=par[par[j][i-1]][i-1];
		len[j][i]=max(len[j][i-1], len[par[j][i-1]][i-1]);
	}
}
int getMinimumFuelCapacity(int X, int Y)
{
	X++; Y++;
	int aans=lca(X, Y);
	aans=max(aans, ans[X]);
	aans=max(aans, ans[Y]);
	if(aans==987654321) aans=-1;
	return aans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 273 ms 42884 KB Output is correct
4 Correct 275 ms 44616 KB Output is correct
5 Correct 288 ms 43640 KB Output is correct
6 Correct 275 ms 44496 KB Output is correct
7 Correct 284 ms 44128 KB Output is correct
8 Correct 274 ms 42640 KB Output is correct
9 Correct 279 ms 43872 KB Output is correct
10 Correct 272 ms 42396 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Incorrect 4 ms 5228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Incorrect 4 ms 5228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Incorrect 4 ms 5228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Incorrect 4 ms 5228 KB Output isn't correct
6 Halted 0 ms 0 KB -