oj.uz

Submission #545157

# Submission time Handle Problem Language Result Execution time Memory
545157 2022-04-03T17:16:49 Z MilosMilutinovic Swapping Cities (APIO20_swap) C++14
7 / 100
 349 ms 39508 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;
	X++; Y++;
	assert(lca(X,Y)>=1&&lca(X,Y)<=n+m);
	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 7380 KB Output is correct
5 Correct 6 ms 7540 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7616 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 101 ms 28632 KB Output is correct
10 Correct 117 ms 33360 KB Output is correct
11 Correct 116 ms 32880 KB Output is correct
12 Correct 125 ms 34464 KB Output is correct
13 Correct 108 ms 35916 KB Output is correct
14 Correct 100 ms 28620 KB Output is correct
15 Correct 165 ms 35228 KB Output is correct
16 Correct 173 ms 34556 KB Output is correct
17 Correct 169 ms 36060 KB Output is correct
18 Correct 156 ms 37692 KB Output is correct
19 Runtime error 59 ms 27228 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #2
7.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 Correct 292 ms 38076 KB Output is correct
4 Correct 309 ms 39508 KB Output is correct
5 Correct 312 ms 38716 KB Output is correct
6 Correct 349 ms 39360 KB Output is correct
7 Correct 302 ms 39116 KB Output is correct
8 Correct 292 ms 37972 KB Output is correct
9 Correct 308 ms 38868 KB Output is correct
10 Correct 320 ms 37768 KB Output is correct

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 7380 KB Output is correct
5 Correct 6 ms 7540 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7616 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Incorrect 4 ms 7636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.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 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7540 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 5 ms 7616 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 101 ms 28632 KB Output is correct
11 Correct 117 ms 33360 KB Output is correct
12 Correct 116 ms 32880 KB Output is correct
13 Correct 125 ms 34464 KB Output is correct
14 Correct 108 ms 35916 KB Output is correct
15 Incorrect 4 ms 7636 KB Output isn't correct
16 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 7380 KB Output is correct
5 Correct 6 ms 7540 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 5 ms 7616 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 101 ms 28632 KB Output is correct
10 Correct 117 ms 33360 KB Output is correct
11 Correct 116 ms 32880 KB Output is correct
12 Correct 125 ms 34464 KB Output is correct
13 Correct 108 ms 35916 KB Output is correct
14 Correct 100 ms 28620 KB Output is correct
15 Correct 165 ms 35228 KB Output is correct
16 Correct 173 ms 34556 KB Output is correct
17 Correct 169 ms 36060 KB Output is correct
18 Correct 156 ms 37692 KB Output is correct
19 Correct 292 ms 38076 KB Output is correct
20 Correct 309 ms 39508 KB Output is correct
21 Correct 312 ms 38716 KB Output is correct
22 Correct 349 ms 39360 KB Output is correct
23 Correct 302 ms 39116 KB Output is correct
24 Correct 292 ms 37972 KB Output is correct
25 Correct 308 ms 38868 KB Output is correct
26 Correct 320 ms 37768 KB Output is correct
27 Incorrect 4 ms 7636 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7540 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 5 ms 7616 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 101 ms 28632 KB Output is correct
11 Correct 117 ms 33360 KB Output is correct
12 Correct 116 ms 32880 KB Output is correct
13 Correct 125 ms 34464 KB Output is correct
14 Correct 108 ms 35916 KB Output is correct
15 Correct 100 ms 28620 KB Output is correct
16 Correct 165 ms 35228 KB Output is correct
17 Correct 173 ms 34556 KB Output is correct
18 Correct 169 ms 36060 KB Output is correct
19 Correct 156 ms 37692 KB Output is correct
20 Correct 292 ms 38076 KB Output is correct
21 Correct 309 ms 39508 KB Output is correct
22 Correct 312 ms 38716 KB Output is correct
23 Correct 349 ms 39360 KB Output is correct
24 Correct 302 ms 39116 KB Output is correct
25 Correct 292 ms 37972 KB Output is correct
26 Correct 308 ms 38868 KB Output is correct
27 Correct 320 ms 37768 KB Output is correct
28 Incorrect 4 ms 7636 KB Output isn't correct
29 Halted 0 ms 0 KB -