답안 #545151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545151	2022-04-03T17:05:39 Z	MilosMilutinovic	자매 도시 (APIO20_swap)	C++14	7 / 100	372 ms	38648 KB

swap

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #545151

Compilation message

Subtask #1 0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0