oj.uz

Submission #545151

# Submission time Handle Problem Language Result Execution time Memory
545151 2022-04-03T17:05:39 Z MilosMilutinovic Swapping Cities (APIO20_swap) C++14
7 / 100
 372 ms 38648 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];
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){
	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){
	X++; Y++;
	int l=lca(X,Y);
	if(ok[l]) return val[l];
	for(int i=19;i>=0;i--) if(f[l][i]!=0&&!ok[f[l][i]]) l=f[l][i];
	return (f[l][0]>0?val[f[l][0]]:-1);
}

/*
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 7300 KB Output is correct
4 Correct 6 ms 7472 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 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 94 ms 27856 KB Output is correct
10 Correct 118 ms 32552 KB Output is correct
11 Correct 140 ms 32140 KB Output is correct
12 Correct 124 ms 33572 KB Output is correct
13 Correct 105 ms 35148 KB Output is correct
14 Correct 114 ms 28052 KB Output is correct
15 Correct 288 ms 34476 KB Output is correct
16 Correct 265 ms 33776 KB Output is correct
17 Correct 295 ms 35304 KB Output is correct
18 Correct 372 ms 36908 KB Output is correct
19 Incorrect 111 ms 14424 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 337 ms 37472 KB Output is correct
4 Correct 357 ms 38648 KB Output is correct
5 Correct 314 ms 38056 KB Output is correct
6 Correct 325 ms 38472 KB Output is correct
7 Correct 311 ms 38444 KB Output is correct
8 Correct 305 ms 37176 KB Output is correct
9 Correct 337 ms 38068 KB Output is correct
10 Correct 304 ms 36976 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 7300 KB Output is correct
4 Correct 6 ms 7472 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 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 7300 KB Output is correct
5 Correct 6 ms 7472 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 6 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 94 ms 27856 KB Output is correct
11 Correct 118 ms 32552 KB Output is correct
12 Correct 140 ms 32140 KB Output is correct
13 Correct 124 ms 33572 KB Output is correct
14 Correct 105 ms 35148 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 7300 KB Output is correct
4 Correct 6 ms 7472 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 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 94 ms 27856 KB Output is correct
10 Correct 118 ms 32552 KB Output is correct
11 Correct 140 ms 32140 KB Output is correct
12 Correct 124 ms 33572 KB Output is correct
13 Correct 105 ms 35148 KB Output is correct
14 Correct 114 ms 28052 KB Output is correct
15 Correct 288 ms 34476 KB Output is correct
16 Correct 265 ms 33776 KB Output is correct
17 Correct 295 ms 35304 KB Output is correct
18 Correct 372 ms 36908 KB Output is correct
19 Correct 337 ms 37472 KB Output is correct
20 Correct 357 ms 38648 KB Output is correct
21 Correct 314 ms 38056 KB Output is correct
22 Correct 325 ms 38472 KB Output is correct
23 Correct 311 ms 38444 KB Output is correct
24 Correct 305 ms 37176 KB Output is correct
25 Correct 337 ms 38068 KB Output is correct
26 Correct 304 ms 36976 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 7300 KB Output is correct
5 Correct 6 ms 7472 KB Output is correct
6 Correct 5 ms 7508 KB Output is correct
7 Correct 6 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 94 ms 27856 KB Output is correct
11 Correct 118 ms 32552 KB Output is correct
12 Correct 140 ms 32140 KB Output is correct
13 Correct 124 ms 33572 KB Output is correct
14 Correct 105 ms 35148 KB Output is correct
15 Correct 114 ms 28052 KB Output is correct
16 Correct 288 ms 34476 KB Output is correct
17 Correct 265 ms 33776 KB Output is correct
18 Correct 295 ms 35304 KB Output is correct
19 Correct 372 ms 36908 KB Output is correct
20 Correct 337 ms 37472 KB Output is correct
21 Correct 357 ms 38648 KB Output is correct
22 Correct 314 ms 38056 KB Output is correct
23 Correct 325 ms 38472 KB Output is correct
24 Correct 311 ms 38444 KB Output is correct
25 Correct 305 ms 37176 KB Output is correct
26 Correct 337 ms 38068 KB Output is correct
27 Correct 304 ms 36976 KB Output is correct
28 Incorrect 5 ms 7636 KB Output isn't correct
29 Halted 0 ms 0 KB -