oj.uz

답안 #897109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897109 2024-01-02T14:43:56 Z LCJLY 자매 도시 (APIO20_swap) C++14
0 / 100
 207 ms 82044 KB 
#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;

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;
int hayden=0;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
	hayden=m;
	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;
}

int getMinimumFuelCapacity(int x, int 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(hayden<=2) assert(cur==root);
	if(cur==root) return -1;
	return cost[two[0][cur]];
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56924 KB Output is correct
4 Correct 10 ms 57012 KB Output is correct
5 Correct 9 ms 57440 KB Output is correct
6 Correct 9 ms 57004 KB Output is correct
7 Correct 9 ms 59228 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 63 ms 68188 KB Output is correct
10 Correct 82 ms 70208 KB Output is correct
11 Correct 79 ms 70224 KB Output is correct
12 Correct 83 ms 70820 KB Output is correct
13 Correct 92 ms 74632 KB Output is correct
14 Correct 71 ms 68436 KB Output is correct
15 Correct 173 ms 72024 KB Output is correct
16 Correct 155 ms 71724 KB Output is correct
17 Correct 162 ms 72564 KB Output is correct
18 Correct 207 ms 76152 KB Output is correct
19 Incorrect 74 ms 64460 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 190 ms 81252 KB Output is correct
4 Correct 184 ms 82044 KB Output is correct
5 Incorrect 173 ms 81652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56924 KB Output is correct
4 Correct 10 ms 57012 KB Output is correct
5 Correct 9 ms 57440 KB Output is correct
6 Correct 9 ms 57004 KB Output is correct
7 Correct 9 ms 59228 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 9 ms 56924 KB Output is correct
10 Correct 9 ms 59228 KB Output is correct
11 Correct 9 ms 59228 KB Output is correct
12 Correct 9 ms 59224 KB Output is correct
13 Correct 9 ms 57180 KB Output is correct
14 Correct 9 ms 57176 KB Output is correct
15 Incorrect 9 ms 59228 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56924 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56920 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 10 ms 57012 KB Output is correct
6 Correct 9 ms 57440 KB Output is correct
7 Correct 9 ms 57004 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 9 ms 59228 KB Output is correct
10 Correct 63 ms 68188 KB Output is correct
11 Correct 82 ms 70208 KB Output is correct
12 Correct 79 ms 70224 KB Output is correct
13 Correct 83 ms 70820 KB Output is correct
14 Correct 92 ms 74632 KB Output is correct
15 Correct 9 ms 59228 KB Output is correct
16 Correct 9 ms 59228 KB Output is correct
17 Correct 9 ms 59224 KB Output is correct
18 Correct 9 ms 57180 KB Output is correct
19 Correct 9 ms 57176 KB Output is correct
20 Incorrect 9 ms 59228 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56920 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56924 KB Output is correct
4 Correct 10 ms 57012 KB Output is correct
5 Correct 9 ms 57440 KB Output is correct
6 Correct 9 ms 57004 KB Output is correct
7 Correct 9 ms 59228 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 63 ms 68188 KB Output is correct
10 Correct 82 ms 70208 KB Output is correct
11 Correct 79 ms 70224 KB Output is correct
12 Correct 83 ms 70820 KB Output is correct
13 Correct 92 ms 74632 KB Output is correct
14 Correct 71 ms 68436 KB Output is correct
15 Correct 173 ms 72024 KB Output is correct
16 Correct 155 ms 71724 KB Output is correct
17 Correct 162 ms 72564 KB Output is correct
18 Correct 207 ms 76152 KB Output is correct
19 Correct 190 ms 81252 KB Output is correct
20 Correct 184 ms 82044 KB Output is correct
21 Incorrect 173 ms 81652 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 56924 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 9 ms 56920 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 10 ms 57012 KB Output is correct
6 Correct 9 ms 57440 KB Output is correct
7 Correct 9 ms 57004 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 9 ms 59228 KB Output is correct
10 Correct 63 ms 68188 KB Output is correct
11 Correct 82 ms 70208 KB Output is correct
12 Correct 79 ms 70224 KB Output is correct
13 Correct 83 ms 70820 KB Output is correct
14 Correct 92 ms 74632 KB Output is correct
15 Correct 71 ms 68436 KB Output is correct
16 Correct 173 ms 72024 KB Output is correct
17 Correct 155 ms 71724 KB Output is correct
18 Correct 162 ms 72564 KB Output is correct
19 Correct 207 ms 76152 KB Output is correct
20 Correct 190 ms 81252 KB Output is correct
21 Correct 184 ms 82044 KB Output is correct
22 Incorrect 173 ms 81652 KB Output isn't correct
23 Halted 0 ms 0 KB -