답안 #545150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545150	2022-04-03T16:59:56 Z	MilosMilutinovic	자매 도시 (APIO20_swap)	C++14	7 / 100	385 ms	42544 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); 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	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

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

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

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

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

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

답안 #545150

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