oj.uz

Submission #545153

# Submission time Handle Problem Language Result Execution time Memory
545153 2022-04-03T17:09:46 Z MilosMilutinovic Swapping Cities (APIO20_swap) C++14
7 / 100
 346 ms 39600 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++;
	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 4 ms 7636 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 104 ms 28556 KB Output is correct
10 Correct 125 ms 33228 KB Output is correct
11 Correct 125 ms 32880 KB Output is correct
12 Correct 121 ms 34380 KB Output is correct
13 Correct 113 ms 35912 KB Output is correct
14 Correct 114 ms 28708 KB Output is correct
15 Correct 172 ms 35224 KB Output is correct
16 Correct 172 ms 34496 KB Output is correct
17 Correct 175 ms 36100 KB Output is correct
18 Correct 155 ms 37608 KB Output is correct
19 Incorrect 102 ms 14548 KB Output isn't correct
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 305 ms 38060 KB Output is correct
4 Correct 346 ms 39600 KB Output is correct
5 Correct 320 ms 38716 KB Output is correct
6 Correct 305 ms 39340 KB Output is correct
7 Correct 335 ms 39144 KB Output is correct
8 Correct 313 ms 38044 KB Output is correct
9 Correct 340 ms 38828 KB Output is correct
10 Correct 308 ms 37704 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 4 ms 7636 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Incorrect 5 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 4 ms 7636 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 104 ms 28556 KB Output is correct
11 Correct 125 ms 33228 KB Output is correct
12 Correct 125 ms 32880 KB Output is correct
13 Correct 121 ms 34380 KB Output is correct
14 Correct 113 ms 35912 KB Output is correct
15 Incorrect 5 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 4 ms 7636 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 4 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 104 ms 28556 KB Output is correct
10 Correct 125 ms 33228 KB Output is correct
11 Correct 125 ms 32880 KB Output is correct
12 Correct 121 ms 34380 KB Output is correct
13 Correct 113 ms 35912 KB Output is correct
14 Correct 114 ms 28708 KB Output is correct
15 Correct 172 ms 35224 KB Output is correct
16 Correct 172 ms 34496 KB Output is correct
17 Correct 175 ms 36100 KB Output is correct
18 Correct 155 ms 37608 KB Output is correct
19 Correct 305 ms 38060 KB Output is correct
20 Correct 346 ms 39600 KB Output is correct
21 Correct 320 ms 38716 KB Output is correct
22 Correct 305 ms 39340 KB Output is correct
23 Correct 335 ms 39144 KB Output is correct
24 Correct 313 ms 38044 KB Output is correct
25 Correct 340 ms 38828 KB Output is correct
26 Correct 308 ms 37704 KB Output is correct
27 Incorrect 5 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 4 ms 7636 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 104 ms 28556 KB Output is correct
11 Correct 125 ms 33228 KB Output is correct
12 Correct 125 ms 32880 KB Output is correct
13 Correct 121 ms 34380 KB Output is correct
14 Correct 113 ms 35912 KB Output is correct
15 Correct 114 ms 28708 KB Output is correct
16 Correct 172 ms 35224 KB Output is correct
17 Correct 172 ms 34496 KB Output is correct
18 Correct 175 ms 36100 KB Output is correct
19 Correct 155 ms 37608 KB Output is correct
20 Correct 305 ms 38060 KB Output is correct
21 Correct 346 ms 39600 KB Output is correct
22 Correct 320 ms 38716 KB Output is correct
23 Correct 305 ms 39340 KB Output is correct
24 Correct 335 ms 39144 KB Output is correct
25 Correct 313 ms 38044 KB Output is correct
26 Correct 340 ms 38828 KB Output is correct
27 Correct 308 ms 37704 KB Output is correct
28 Incorrect 5 ms 7636 KB Output isn't correct
29 Halted 0 ms 0 KB -