답안 #897114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897114	2024-01-02T14:53:25 Z	LCJLY	자매 도시 (APIO20_swap)	C++14	0 / 100	633 ms	127860 KB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
#define int long long

vector<int>adj[500005];
long long cost[500005];

struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	
	int get(int x){return e[x]<0?x:e[x]=get(e[x]);}
	
	bool unite(int x, int y){ //x is par
		x=get(x),y=get(y);
		if(x==y) return 0;
		adj[x].push_back(y);
		adj[y].push_back(x);
		e[x]+=e[y];
		e[y]=x;
		return 1;
	}
};

int two[22][500005];
int d[500005];
void dfs(int index, int par){
	for(int x=0;x<20;x++){
		if(two[x][index]==-1) break;
		two[x+1][index]=two[x][two[x][index]];
	}
	
	for(auto it:adj[index]){
		if(it==par) continue;
		two[0][it]=index;
		d[it]=d[index]+1;
		dfs(it,index);
	}
}

int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<20;x++){
		if(diff&(1<<x)) b=two[x][b];
	}
	
	if(a==b) return a;
	for(int x=19;x>=0;x--){
		if(two[x][b]!=two[x][a]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
}

bool done[300005];


int root=0;
void init(int32_t n, int32_t m, vector<int32_t> u, vector<int32_t> v, vector<int32_t> w){
	pair<int,pii>edge[m];
	for(int x=0;x<m;x++){
		edge[x].first=w[x];
		edge[x].second={u[x],v[x]};
	}
	
	sort(edge,edge+m);
	
	DSU dsu;
	dsu.init(n+m+20);
	
	int in[n+5];
	memset(in,0,sizeof(in));
	
	for(int x=0;x<m;x++){
		int l=edge[x].second.first;
		int r=edge[x].second.second;
		int hold=edge[x].first;
		in[l]++;
		in[r]++;
		
		if(in[l]>2||in[r]>2) done[n+x+1]=true;
		l=dsu.get(l);
		r=dsu.get(r);
		if(l==r||done[l]||done[r]) done[n+x+1]=true;
		dsu.unite(n+x+1,l);
		dsu.unite(n+x+1,r);
		cost[n+x+1]=hold;
	}
	
	memset(two,-1,sizeof(two));
	
	dfs(n+m,-1);
	root=n+m;
}

int32_t getMinimumFuelCapacity(int32_t x, int32_t y){
	int hold=lca(x,y);
	
	if(done[hold]){
		return cost[hold];
	}
	
	int cur=hold;
	for(int bit=19;bit>=0;bit--){
		if(d[hold]&(1<<bit)){
			if(!done[two[bit][cur]]){
				cur=two[bit][cur];
			}
		}
	}
	if(cur==root) return -1;
	return cost[two[0][cur]];
}

Subtask #1
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	101980 KB	Output is correct
2	Correct	14 ms	102044 KB	Output is correct
3	Correct	13 ms	101980 KB	Output is correct
4	Correct	14 ms	101976 KB	Output is correct
5	Correct	14 ms	102236 KB	Output is correct
6	Correct	14 ms	102132 KB	Output is correct
7	Correct	14 ms	102236 KB	Output is correct
8	Correct	14 ms	102216 KB	Output is correct
9	Correct	85 ms	116768 KB	Output is correct
10	Correct	100 ms	119364 KB	Output is correct
11	Correct	106 ms	119124 KB	Output is correct
12	Correct	105 ms	120040 KB	Output is correct
13	Correct	105 ms	122940 KB	Output is correct
14	Correct	130 ms	117144 KB	Output is correct
15	Correct	450 ms	121168 KB	Output is correct
16	Correct	498 ms	120984 KB	Output is correct
17	Correct	517 ms	121584 KB	Output is correct
18	Correct	633 ms	124540 KB	Output is correct
19	Incorrect	114 ms	109880 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	101980 KB	Output is correct
2	Correct	14 ms	102044 KB	Output is correct
3	Correct	574 ms	127036 KB	Output is correct
4	Correct	573 ms	127860 KB	Output is correct
5	Incorrect	630 ms	127408 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	101980 KB	Output is correct
2	Correct	14 ms	102044 KB	Output is correct
3	Correct	13 ms	101980 KB	Output is correct
4	Correct	14 ms	101976 KB	Output is correct
5	Correct	14 ms	102236 KB	Output is correct
6	Correct	14 ms	102132 KB	Output is correct
7	Correct	14 ms	102236 KB	Output is correct
8	Correct	14 ms	102216 KB	Output is correct
9	Correct	15 ms	101980 KB	Output is correct
10	Correct	14 ms	102152 KB	Output is correct
11	Correct	14 ms	102168 KB	Output is correct
12	Correct	15 ms	102236 KB	Output is correct
13	Correct	14 ms	102236 KB	Output is correct
14	Correct	14 ms	102084 KB	Output is correct
15	Incorrect	17 ms	102232 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	101980 KB	Output is correct
2	Correct	26 ms	101980 KB	Output is correct
3	Correct	14 ms	102044 KB	Output is correct
4	Correct	13 ms	101980 KB	Output is correct
5	Correct	14 ms	101976 KB	Output is correct
6	Correct	14 ms	102236 KB	Output is correct
7	Correct	14 ms	102132 KB	Output is correct
8	Correct	14 ms	102236 KB	Output is correct
9	Correct	14 ms	102216 KB	Output is correct
10	Correct	85 ms	116768 KB	Output is correct
11	Correct	100 ms	119364 KB	Output is correct
12	Correct	106 ms	119124 KB	Output is correct
13	Correct	105 ms	120040 KB	Output is correct
14	Correct	105 ms	122940 KB	Output is correct
15	Correct	14 ms	102152 KB	Output is correct
16	Correct	14 ms	102168 KB	Output is correct
17	Correct	15 ms	102236 KB	Output is correct
18	Correct	14 ms	102236 KB	Output is correct
19	Correct	14 ms	102084 KB	Output is correct
20	Incorrect	17 ms	102232 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	101980 KB	Output is correct
2	Correct	14 ms	102044 KB	Output is correct
3	Correct	13 ms	101980 KB	Output is correct
4	Correct	14 ms	101976 KB	Output is correct
5	Correct	14 ms	102236 KB	Output is correct
6	Correct	14 ms	102132 KB	Output is correct
7	Correct	14 ms	102236 KB	Output is correct
8	Correct	14 ms	102216 KB	Output is correct
9	Correct	85 ms	116768 KB	Output is correct
10	Correct	100 ms	119364 KB	Output is correct
11	Correct	106 ms	119124 KB	Output is correct
12	Correct	105 ms	120040 KB	Output is correct
13	Correct	105 ms	122940 KB	Output is correct
14	Correct	130 ms	117144 KB	Output is correct
15	Correct	450 ms	121168 KB	Output is correct
16	Correct	498 ms	120984 KB	Output is correct
17	Correct	517 ms	121584 KB	Output is correct
18	Correct	633 ms	124540 KB	Output is correct
19	Correct	574 ms	127036 KB	Output is correct
20	Correct	573 ms	127860 KB	Output is correct
21	Incorrect	630 ms	127408 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	101980 KB	Output is correct
2	Correct	26 ms	101980 KB	Output is correct
3	Correct	14 ms	102044 KB	Output is correct
4	Correct	13 ms	101980 KB	Output is correct
5	Correct	14 ms	101976 KB	Output is correct
6	Correct	14 ms	102236 KB	Output is correct
7	Correct	14 ms	102132 KB	Output is correct
8	Correct	14 ms	102236 KB	Output is correct
9	Correct	14 ms	102216 KB	Output is correct
10	Correct	85 ms	116768 KB	Output is correct
11	Correct	100 ms	119364 KB	Output is correct
12	Correct	106 ms	119124 KB	Output is correct
13	Correct	105 ms	120040 KB	Output is correct
14	Correct	105 ms	122940 KB	Output is correct
15	Correct	130 ms	117144 KB	Output is correct
16	Correct	450 ms	121168 KB	Output is correct
17	Correct	498 ms	120984 KB	Output is correct
18	Correct	517 ms	121584 KB	Output is correct
19	Correct	633 ms	124540 KB	Output is correct
20	Correct	574 ms	127036 KB	Output is correct
21	Correct	573 ms	127860 KB	Output is correct
22	Incorrect	630 ms	127408 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

답안 #897114

Compilation message

Subtask #1 0 / 6.0

Subtask #2 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
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0