oj.uz

Submission #545154

# Submission time Handle Problem Language Result Execution time Memory
545154 2022-04-03T17:14:56 Z MilosMilutinovic Swapping Cities (APIO20_swap) C++14
0 / 100
 233 ms 73388 KB 
#include "swap.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

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

template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}

int n,m,fa[300005],f[300005][20],val[300005],dep[300005],tl[300005],tr[300005],ok[300005],up[300005];
array<int,3> edg[200005];
vector<int> adj[300005];

int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);}

void dfs(int u,int p){
	up[u]=(ok[u]?u:up[p]);
	dep[u]=dep[p]+1;
	f[u][0]=p;
	for(int i=1;i<20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int v:adj[u]) dfs(v,u);
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[x][i];
	return f[x][0];
}

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++) edg[i+1]={W[i],U[i]+1,V[i]+1};
	sort(edg+1,edg+m+1);
	for(int i=1;i<=n;i++) tl[i]=tr[i]=i;
	for(int i=1;i<=n+m;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=edg[i][1],v=edg[i][2],w=edg[i][0];
		val[n+i]=w;
		u=getf(u); v=getf(v); fa[u]=fa[v]=n+i;
		ok[n+i]=(ok[u]|ok[v]|(u==v?1:0));
		bool found=false;
		for(int x:{tl[u],tr[u]}){
			for(int y:{tl[v],tr[v]}){
				if((x==edg[i][1]&&y==edg[i][2])||(x==edg[i][2]&&y==edg[i][1])){
					found=true; tl[n+i]=(x^tl[u]^tr[u]); tr[n+i]=(y^tl[v]^tr[v]);
				}
			}
		}
		if(!found) ok[n+i]=1;
		adj[n+i].pb(u); if(u!=v) adj[n+i].pb(v);
	}
	dfs(n+m,0);
}

int getMinimumFuelCapacity(int X,int Y){
	if(!ok[n+m]) return -1;
	assert(lca(X,Y)>=1&&lca(X,Y)<=n+m&&up[lca(X,Y)]>=1&&up[lca(X,Y)]<=n+m);
	X++; Y++;
	return val[up[lca(X,Y)]];
}

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7392 KB Output is correct
5 Correct 6 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 96 ms 28544 KB Output is correct
10 Correct 117 ms 33184 KB Output is correct
11 Correct 119 ms 32772 KB Output is correct
12 Correct 128 ms 34344 KB Output is correct
13 Correct 114 ms 35912 KB Output is correct
14 Correct 100 ms 28620 KB Output is correct
15 Correct 173 ms 35276 KB Output is correct
16 Correct 166 ms 34684 KB Output is correct
17 Correct 183 ms 36068 KB Output is correct
18 Correct 157 ms 37716 KB Output is correct
19 Runtime error 57 ms 27220 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Runtime error 233 ms 73388 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7392 KB Output is correct
5 Correct 6 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Runtime error 10 ms 14804 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 14804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7392 KB Output is correct
5 Correct 6 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 96 ms 28544 KB Output is correct
10 Correct 117 ms 33184 KB Output is correct
11 Correct 119 ms 32772 KB Output is correct
12 Correct 128 ms 34344 KB Output is correct
13 Correct 114 ms 35912 KB Output is correct
14 Correct 100 ms 28620 KB Output is correct
15 Correct 173 ms 35276 KB Output is correct
16 Correct 166 ms 34684 KB Output is correct
17 Correct 183 ms 36068 KB Output is correct
18 Correct 157 ms 37716 KB Output is correct
19 Runtime error 233 ms 73388 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 14804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -