답안 #545157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545157	2022-04-03T17:16:49 Z	MilosMilutinovic	자매 도시 (APIO20_swap)	C++14	7 / 100	349 ms	39508 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);
	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	4 ms	7380 KB	Output is correct
5	Correct	6 ms	7540 KB	Output is correct
6	Correct	5 ms	7508 KB	Output is correct
7	Correct	5 ms	7616 KB	Output is correct
8	Correct	5 ms	7636 KB	Output is correct
9	Correct	101 ms	28632 KB	Output is correct
10	Correct	117 ms	33360 KB	Output is correct
11	Correct	116 ms	32880 KB	Output is correct
12	Correct	125 ms	34464 KB	Output is correct
13	Correct	108 ms	35916 KB	Output is correct
14	Correct	100 ms	28620 KB	Output is correct
15	Correct	165 ms	35228 KB	Output is correct
16	Correct	173 ms	34556 KB	Output is correct
17	Correct	169 ms	36060 KB	Output is correct
18	Correct	156 ms	37692 KB	Output is correct
19	Runtime error	59 ms	27228 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	292 ms	38076 KB	Output is correct
4	Correct	309 ms	39508 KB	Output is correct
5	Correct	312 ms	38716 KB	Output is correct
6	Correct	349 ms	39360 KB	Output is correct
7	Correct	302 ms	39116 KB	Output is correct
8	Correct	292 ms	37972 KB	Output is correct
9	Correct	308 ms	38868 KB	Output is correct
10	Correct	320 ms	37768 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	4 ms	7380 KB	Output is correct
5	Correct	6 ms	7540 KB	Output is correct
6	Correct	5 ms	7508 KB	Output is correct
7	Correct	5 ms	7616 KB	Output is correct
8	Correct	5 ms	7636 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Incorrect	4 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	4 ms	7380 KB	Output is correct
6	Correct	6 ms	7540 KB	Output is correct
7	Correct	5 ms	7508 KB	Output is correct
8	Correct	5 ms	7616 KB	Output is correct
9	Correct	5 ms	7636 KB	Output is correct
10	Correct	101 ms	28632 KB	Output is correct
11	Correct	117 ms	33360 KB	Output is correct
12	Correct	116 ms	32880 KB	Output is correct
13	Correct	125 ms	34464 KB	Output is correct
14	Correct	108 ms	35916 KB	Output is correct
15	Incorrect	4 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	4 ms	7380 KB	Output is correct
5	Correct	6 ms	7540 KB	Output is correct
6	Correct	5 ms	7508 KB	Output is correct
7	Correct	5 ms	7616 KB	Output is correct
8	Correct	5 ms	7636 KB	Output is correct
9	Correct	101 ms	28632 KB	Output is correct
10	Correct	117 ms	33360 KB	Output is correct
11	Correct	116 ms	32880 KB	Output is correct
12	Correct	125 ms	34464 KB	Output is correct
13	Correct	108 ms	35916 KB	Output is correct
14	Correct	100 ms	28620 KB	Output is correct
15	Correct	165 ms	35228 KB	Output is correct
16	Correct	173 ms	34556 KB	Output is correct
17	Correct	169 ms	36060 KB	Output is correct
18	Correct	156 ms	37692 KB	Output is correct
19	Correct	292 ms	38076 KB	Output is correct
20	Correct	309 ms	39508 KB	Output is correct
21	Correct	312 ms	38716 KB	Output is correct
22	Correct	349 ms	39360 KB	Output is correct
23	Correct	302 ms	39116 KB	Output is correct
24	Correct	292 ms	37972 KB	Output is correct
25	Correct	308 ms	38868 KB	Output is correct
26	Correct	320 ms	37768 KB	Output is correct
27	Incorrect	4 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	4 ms	7380 KB	Output is correct
6	Correct	6 ms	7540 KB	Output is correct
7	Correct	5 ms	7508 KB	Output is correct
8	Correct	5 ms	7616 KB	Output is correct
9	Correct	5 ms	7636 KB	Output is correct
10	Correct	101 ms	28632 KB	Output is correct
11	Correct	117 ms	33360 KB	Output is correct
12	Correct	116 ms	32880 KB	Output is correct
13	Correct	125 ms	34464 KB	Output is correct
14	Correct	108 ms	35916 KB	Output is correct
15	Correct	100 ms	28620 KB	Output is correct
16	Correct	165 ms	35228 KB	Output is correct
17	Correct	173 ms	34556 KB	Output is correct
18	Correct	169 ms	36060 KB	Output is correct
19	Correct	156 ms	37692 KB	Output is correct
20	Correct	292 ms	38076 KB	Output is correct
21	Correct	309 ms	39508 KB	Output is correct
22	Correct	312 ms	38716 KB	Output is correct
23	Correct	349 ms	39360 KB	Output is correct
24	Correct	302 ms	39116 KB	Output is correct
25	Correct	292 ms	37972 KB	Output is correct
26	Correct	308 ms	38868 KB	Output is correct
27	Correct	320 ms	37768 KB	Output is correct
28	Incorrect	4 ms	7636 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #545157

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