답안 #545153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545153	2022-04-03T17:09:46 Z	MilosMilutinovic	자매 도시 (APIO20_swap)	C++14	7 / 100	346 ms	39600 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++;
	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	4 ms	7636 KB	Output is correct
6	Correct	5 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	104 ms	28556 KB	Output is correct
10	Correct	125 ms	33228 KB	Output is correct
11	Correct	125 ms	32880 KB	Output is correct
12	Correct	121 ms	34380 KB	Output is correct
13	Correct	113 ms	35912 KB	Output is correct
14	Correct	114 ms	28708 KB	Output is correct
15	Correct	172 ms	35224 KB	Output is correct
16	Correct	172 ms	34496 KB	Output is correct
17	Correct	175 ms	36100 KB	Output is correct
18	Correct	155 ms	37608 KB	Output is correct
19	Incorrect	102 ms	14548 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	305 ms	38060 KB	Output is correct
4	Correct	346 ms	39600 KB	Output is correct
5	Correct	320 ms	38716 KB	Output is correct
6	Correct	305 ms	39340 KB	Output is correct
7	Correct	335 ms	39144 KB	Output is correct
8	Correct	313 ms	38044 KB	Output is correct
9	Correct	340 ms	38828 KB	Output is correct
10	Correct	308 ms	37704 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	4 ms	7636 KB	Output is correct
6	Correct	5 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	7380 KB	Output is correct
5	Correct	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7636 KB	Output is correct
7	Correct	5 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	104 ms	28556 KB	Output is correct
11	Correct	125 ms	33228 KB	Output is correct
12	Correct	125 ms	32880 KB	Output is correct
13	Correct	121 ms	34380 KB	Output is correct
14	Correct	113 ms	35912 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	4 ms	7380 KB	Output is correct
5	Correct	4 ms	7636 KB	Output is correct
6	Correct	5 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	104 ms	28556 KB	Output is correct
10	Correct	125 ms	33228 KB	Output is correct
11	Correct	125 ms	32880 KB	Output is correct
12	Correct	121 ms	34380 KB	Output is correct
13	Correct	113 ms	35912 KB	Output is correct
14	Correct	114 ms	28708 KB	Output is correct
15	Correct	172 ms	35224 KB	Output is correct
16	Correct	172 ms	34496 KB	Output is correct
17	Correct	175 ms	36100 KB	Output is correct
18	Correct	155 ms	37608 KB	Output is correct
19	Correct	305 ms	38060 KB	Output is correct
20	Correct	346 ms	39600 KB	Output is correct
21	Correct	320 ms	38716 KB	Output is correct
22	Correct	305 ms	39340 KB	Output is correct
23	Correct	335 ms	39144 KB	Output is correct
24	Correct	313 ms	38044 KB	Output is correct
25	Correct	340 ms	38828 KB	Output is correct
26	Correct	308 ms	37704 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	4 ms	7380 KB	Output is correct
6	Correct	4 ms	7636 KB	Output is correct
7	Correct	5 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	104 ms	28556 KB	Output is correct
11	Correct	125 ms	33228 KB	Output is correct
12	Correct	125 ms	32880 KB	Output is correct
13	Correct	121 ms	34380 KB	Output is correct
14	Correct	113 ms	35912 KB	Output is correct
15	Correct	114 ms	28708 KB	Output is correct
16	Correct	172 ms	35224 KB	Output is correct
17	Correct	172 ms	34496 KB	Output is correct
18	Correct	175 ms	36100 KB	Output is correct
19	Correct	155 ms	37608 KB	Output is correct
20	Correct	305 ms	38060 KB	Output is correct
21	Correct	346 ms	39600 KB	Output is correct
22	Correct	320 ms	38716 KB	Output is correct
23	Correct	305 ms	39340 KB	Output is correct
24	Correct	335 ms	39144 KB	Output is correct
25	Correct	313 ms	38044 KB	Output is correct
26	Correct	340 ms	38828 KB	Output is correct
27	Correct	308 ms	37704 KB	Output is correct
28	Incorrect	5 ms	7636 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #545153

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