oj.uz

Submission #545150

# Submission time Handle Problem Language Result Execution time Memory
545150 2022-04-03T16:59:56 Z MilosMilutinovic Swapping Cities (APIO20_swap) C++14
7 / 100
 385 ms 42544 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); 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 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 5 ms 7488 KB Output is correct
5 Correct 5 ms 7640 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 98 ms 29648 KB Output is correct
10 Correct 120 ms 34508 KB Output is correct
11 Correct 119 ms 34044 KB Output is correct
12 Correct 140 ms 35792 KB Output is correct
13 Correct 104 ms 37184 KB Output is correct
14 Correct 108 ms 29908 KB Output is correct
15 Correct 260 ms 38824 KB Output is correct
16 Correct 263 ms 38084 KB Output is correct
17 Correct 310 ms 39840 KB Output is correct
18 Correct 385 ms 41288 KB Output is correct
19 Incorrect 118 ms 16428 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 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 326 ms 41160 KB Output is correct
4 Correct 318 ms 42544 KB Output is correct
5 Correct 385 ms 42012 KB Output is correct
6 Correct 303 ms 42380 KB Output is correct
7 Correct 326 ms 42428 KB Output is correct
8 Correct 357 ms 41088 KB Output is correct
9 Correct 335 ms 41940 KB Output is correct
10 Correct 317 ms 40836 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 5 ms 7488 KB Output is correct
5 Correct 5 ms 7640 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 5 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 7628 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 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7368 KB Output is correct
5 Correct 5 ms 7488 KB Output is correct
6 Correct 5 ms 7640 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 98 ms 29648 KB Output is correct
11 Correct 120 ms 34508 KB Output is correct
12 Correct 119 ms 34044 KB Output is correct
13 Correct 140 ms 35792 KB Output is correct
14 Correct 104 ms 37184 KB Output is correct
15 Incorrect 5 ms 7628 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7368 KB Output is correct
4 Correct 5 ms 7488 KB Output is correct
5 Correct 5 ms 7640 KB Output is correct
6 Correct 5 ms 7636 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 98 ms 29648 KB Output is correct
10 Correct 120 ms 34508 KB Output is correct
11 Correct 119 ms 34044 KB Output is correct
12 Correct 140 ms 35792 KB Output is correct
13 Correct 104 ms 37184 KB Output is correct
14 Correct 108 ms 29908 KB Output is correct
15 Correct 260 ms 38824 KB Output is correct
16 Correct 263 ms 38084 KB Output is correct
17 Correct 310 ms 39840 KB Output is correct
18 Correct 385 ms 41288 KB Output is correct
19 Correct 326 ms 41160 KB Output is correct
20 Correct 318 ms 42544 KB Output is correct
21 Correct 385 ms 42012 KB Output is correct
22 Correct 303 ms 42380 KB Output is correct
23 Correct 326 ms 42428 KB Output is correct
24 Correct 357 ms 41088 KB Output is correct
25 Correct 335 ms 41940 KB Output is correct
26 Correct 317 ms 40836 KB Output is correct
27 Incorrect 5 ms 7628 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 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7368 KB Output is correct
5 Correct 5 ms 7488 KB Output is correct
6 Correct 5 ms 7640 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 5 ms 7636 KB Output is correct
10 Correct 98 ms 29648 KB Output is correct
11 Correct 120 ms 34508 KB Output is correct
12 Correct 119 ms 34044 KB Output is correct
13 Correct 140 ms 35792 KB Output is correct
14 Correct 104 ms 37184 KB Output is correct
15 Correct 108 ms 29908 KB Output is correct
16 Correct 260 ms 38824 KB Output is correct
17 Correct 263 ms 38084 KB Output is correct
18 Correct 310 ms 39840 KB Output is correct
19 Correct 385 ms 41288 KB Output is correct
20 Correct 326 ms 41160 KB Output is correct
21 Correct 318 ms 42544 KB Output is correct
22 Correct 385 ms 42012 KB Output is correct
23 Correct 303 ms 42380 KB Output is correct
24 Correct 326 ms 42428 KB Output is correct
25 Correct 357 ms 41088 KB Output is correct
26 Correct 335 ms 41940 KB Output is correct
27 Correct 317 ms 40836 KB Output is correct
28 Incorrect 5 ms 7628 KB Output isn't correct
29 Halted 0 ms 0 KB -