oj.uz

답안 #897098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897098 2024-01-02T14:37:19 Z LCJLY 자매 도시 (APIO20_swap) C++14
0 / 100
 196 ms 82040 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;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> 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;
}

int getMinimumFuelCapacity(int x, int y){
	int hold=lca(x,y);
	
	if(done[hold]){
		return cost[hold];
	}
	
	int cur=hold;
	for(int x=19;x>=0;x--){
		if(d[hold]&(1<<x)){
			if(!done[two[x][cur]]){
				cur=two[x][cur];
			}
		}
	}
	
	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 8 ms 56920 KB Output is correct
3 Correct 8 ms 57060 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 10 ms 57224 KB Output is correct
7 Correct 10 ms 59224 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 64 ms 68252 KB Output is correct
10 Correct 106 ms 70452 KB Output is correct
11 Correct 78 ms 70180 KB Output is correct
12 Correct 83 ms 70920 KB Output is correct
13 Correct 111 ms 74576 KB Output is correct
14 Correct 86 ms 68436 KB Output is correct
15 Correct 168 ms 72020 KB Output is correct
16 Correct 152 ms 71768 KB Output is correct
17 Correct 168 ms 72276 KB Output is correct
18 Correct 196 ms 76368 KB Output is correct
19 Incorrect 74 ms 64336 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 8 ms 56920 KB Output is correct
3 Correct 172 ms 81124 KB Output is correct
4 Correct 182 ms 82040 KB Output is correct
5 Incorrect 172 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 8 ms 56920 KB Output is correct
3 Correct 8 ms 57060 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 10 ms 57224 KB Output is correct
7 Correct 10 ms 59224 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 8 ms 56924 KB Output is correct
10 Correct 9 ms 59056 KB Output is correct
11 Correct 9 ms 59228 KB Output is correct
12 Correct 10 ms 59228 KB Output is correct
13 Correct 9 ms 57072 KB Output is correct
14 Correct 9 ms 57180 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 8 ms 56924 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 8 ms 56920 KB Output is correct
4 Correct 8 ms 57060 KB Output is correct
5 Correct 9 ms 56924 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 10 ms 57224 KB Output is correct
8 Correct 10 ms 59224 KB Output is correct
9 Correct 9 ms 59228 KB Output is correct
10 Correct 64 ms 68252 KB Output is correct
11 Correct 106 ms 70452 KB Output is correct
12 Correct 78 ms 70180 KB Output is correct
13 Correct 83 ms 70920 KB Output is correct
14 Correct 111 ms 74576 KB Output is correct
15 Correct 9 ms 59056 KB Output is correct
16 Correct 9 ms 59228 KB Output is correct
17 Correct 10 ms 59228 KB Output is correct
18 Correct 9 ms 57072 KB Output is correct
19 Correct 9 ms 57180 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 8 ms 56920 KB Output is correct
3 Correct 8 ms 57060 KB Output is correct
4 Correct 9 ms 56924 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 10 ms 57224 KB Output is correct
7 Correct 10 ms 59224 KB Output is correct
8 Correct 9 ms 59228 KB Output is correct
9 Correct 64 ms 68252 KB Output is correct
10 Correct 106 ms 70452 KB Output is correct
11 Correct 78 ms 70180 KB Output is correct
12 Correct 83 ms 70920 KB Output is correct
13 Correct 111 ms 74576 KB Output is correct
14 Correct 86 ms 68436 KB Output is correct
15 Correct 168 ms 72020 KB Output is correct
16 Correct 152 ms 71768 KB Output is correct
17 Correct 168 ms 72276 KB Output is correct
18 Correct 196 ms 76368 KB Output is correct
19 Correct 172 ms 81124 KB Output is correct
20 Correct 182 ms 82040 KB Output is correct
21 Incorrect 172 ms 81652 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 56924 KB Output is correct
2 Correct 9 ms 56920 KB Output is correct
3 Correct 8 ms 56920 KB Output is correct
4 Correct 8 ms 57060 KB Output is correct
5 Correct 9 ms 56924 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 10 ms 57224 KB Output is correct
8 Correct 10 ms 59224 KB Output is correct
9 Correct 9 ms 59228 KB Output is correct
10 Correct 64 ms 68252 KB Output is correct
11 Correct 106 ms 70452 KB Output is correct
12 Correct 78 ms 70180 KB Output is correct
13 Correct 83 ms 70920 KB Output is correct
14 Correct 111 ms 74576 KB Output is correct
15 Correct 86 ms 68436 KB Output is correct
16 Correct 168 ms 72020 KB Output is correct
17 Correct 152 ms 71768 KB Output is correct
18 Correct 168 ms 72276 KB Output is correct
19 Correct 196 ms 76368 KB Output is correct
20 Correct 172 ms 81124 KB Output is correct
21 Correct 182 ms 82040 KB Output is correct
22 Incorrect 172 ms 81652 KB Output isn't correct
23 Halted 0 ms 0 KB -