답안 #545156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545156	2022-04-03T17:15:54 Z	MilosMilutinovic	자매 도시 (APIO20_swap)	C++14	7 / 100	379 ms	39476 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],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&&up[lca(X,Y)]>=1&&up[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

#	결과	실행 시간	메모리	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	6 ms	7380 KB	Output is correct
5	Correct	6 ms	7636 KB	Output is correct
6	Correct	5 ms	7508 KB	Output is correct
7	Correct	5 ms	7636 KB	Output is correct
8	Correct	4 ms	7636 KB	Output is correct
9	Correct	108 ms	28556 KB	Output is correct
10	Correct	138 ms	33312 KB	Output is correct
11	Correct	141 ms	32828 KB	Output is correct
12	Correct	136 ms	34348 KB	Output is correct
13	Correct	141 ms	35932 KB	Output is correct
14	Correct	110 ms	28620 KB	Output is correct
15	Correct	188 ms	35288 KB	Output is correct
16	Correct	171 ms	34516 KB	Output is correct
17	Correct	253 ms	36072 KB	Output is correct
18	Correct	159 ms	37716 KB	Output is correct
19	Runtime error	56 ms	27244 KB	Execution killed with signal 6
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	348 ms	38072 KB	Output is correct
4	Correct	319 ms	39476 KB	Output is correct
5	Correct	354 ms	38720 KB	Output is correct
6	Correct	351 ms	39356 KB	Output is correct
7	Correct	379 ms	39152 KB	Output is correct
8	Correct	359 ms	37952 KB	Output is correct
9	Correct	374 ms	38828 KB	Output is correct
10	Correct	345 ms	37692 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	7380 KB	Output is correct
4	Correct	6 ms	7380 KB	Output is correct
5	Correct	6 ms	7636 KB	Output is correct
6	Correct	5 ms	7508 KB	Output is correct
7	Correct	5 ms	7636 KB	Output is correct
8	Correct	4 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	7380 KB	Output is correct
5	Correct	6 ms	7380 KB	Output is correct
6	Correct	6 ms	7636 KB	Output is correct
7	Correct	5 ms	7508 KB	Output is correct
8	Correct	5 ms	7636 KB	Output is correct
9	Correct	4 ms	7636 KB	Output is correct
10	Correct	108 ms	28556 KB	Output is correct
11	Correct	138 ms	33312 KB	Output is correct
12	Correct	141 ms	32828 KB	Output is correct
13	Correct	136 ms	34348 KB	Output is correct
14	Correct	141 ms	35932 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	7380 KB	Output is correct
4	Correct	6 ms	7380 KB	Output is correct
5	Correct	6 ms	7636 KB	Output is correct
6	Correct	5 ms	7508 KB	Output is correct
7	Correct	5 ms	7636 KB	Output is correct
8	Correct	4 ms	7636 KB	Output is correct
9	Correct	108 ms	28556 KB	Output is correct
10	Correct	138 ms	33312 KB	Output is correct
11	Correct	141 ms	32828 KB	Output is correct
12	Correct	136 ms	34348 KB	Output is correct
13	Correct	141 ms	35932 KB	Output is correct
14	Correct	110 ms	28620 KB	Output is correct
15	Correct	188 ms	35288 KB	Output is correct
16	Correct	171 ms	34516 KB	Output is correct
17	Correct	253 ms	36072 KB	Output is correct
18	Correct	159 ms	37716 KB	Output is correct
19	Correct	348 ms	38072 KB	Output is correct
20	Correct	319 ms	39476 KB	Output is correct
21	Correct	354 ms	38720 KB	Output is correct
22	Correct	351 ms	39356 KB	Output is correct
23	Correct	379 ms	39152 KB	Output is correct
24	Correct	359 ms	37952 KB	Output is correct
25	Correct	374 ms	38828 KB	Output is correct
26	Correct	345 ms	37692 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	7380 KB	Output is correct
5	Correct	6 ms	7380 KB	Output is correct
6	Correct	6 ms	7636 KB	Output is correct
7	Correct	5 ms	7508 KB	Output is correct
8	Correct	5 ms	7636 KB	Output is correct
9	Correct	4 ms	7636 KB	Output is correct
10	Correct	108 ms	28556 KB	Output is correct
11	Correct	138 ms	33312 KB	Output is correct
12	Correct	141 ms	32828 KB	Output is correct
13	Correct	136 ms	34348 KB	Output is correct
14	Correct	141 ms	35932 KB	Output is correct
15	Correct	110 ms	28620 KB	Output is correct
16	Correct	188 ms	35288 KB	Output is correct
17	Correct	171 ms	34516 KB	Output is correct
18	Correct	253 ms	36072 KB	Output is correct
19	Correct	159 ms	37716 KB	Output is correct
20	Correct	348 ms	38072 KB	Output is correct
21	Correct	319 ms	39476 KB	Output is correct
22	Correct	354 ms	38720 KB	Output is correct
23	Correct	351 ms	39356 KB	Output is correct
24	Correct	379 ms	39152 KB	Output is correct
25	Correct	359 ms	37952 KB	Output is correct
26	Correct	374 ms	38828 KB	Output is correct
27	Correct	345 ms	37692 KB	Output is correct
28	Incorrect	5 ms	7636 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #545156

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