oj.uz

답안 #897115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
897115 2024-01-02T14:56:18 Z LCJLY 자매 도시 (APIO20_swap) C++14
0 / 100
 596 ms 128084 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;
#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(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 30 ms 101968 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 14 ms 102224 KB Output is correct
7 Correct 14 ms 102236 KB Output is correct
8 Correct 14 ms 102236 KB Output is correct
9 Correct 84 ms 116640 KB Output is correct
10 Correct 103 ms 119460 KB Output is correct
11 Correct 92 ms 119120 KB Output is correct
12 Correct 107 ms 120024 KB Output is correct
13 Correct 108 ms 122964 KB Output is correct
14 Correct 109 ms 116708 KB Output is correct
15 Correct 476 ms 121172 KB Output is correct
16 Correct 463 ms 120656 KB Output is correct
17 Correct 521 ms 121584 KB Output is correct
18 Correct 539 ms 124500 KB Output is correct
19 Incorrect 118 ms 108632 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 101968 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 563 ms 127064 KB Output is correct
4 Correct 592 ms 128084 KB Output is correct
5 Incorrect 596 ms 127372 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 101968 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 14 ms 102224 KB Output is correct
7 Correct 14 ms 102236 KB Output is correct
8 Correct 14 ms 102236 KB Output is correct
9 Correct 15 ms 101976 KB Output is correct
10 Correct 15 ms 102236 KB Output is correct
11 Correct 16 ms 102184 KB Output is correct
12 Correct 16 ms 102236 KB Output is correct
13 Correct 16 ms 102392 KB Output is correct
14 Correct 14 ms 102232 KB Output is correct
15 Incorrect 15 ms 102232 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 101976 KB Output is correct
2 Correct 30 ms 101968 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 101980 KB Output is correct
6 Correct 14 ms 102236 KB Output is correct
7 Correct 14 ms 102224 KB Output is correct
8 Correct 14 ms 102236 KB Output is correct
9 Correct 14 ms 102236 KB Output is correct
10 Correct 84 ms 116640 KB Output is correct
11 Correct 103 ms 119460 KB Output is correct
12 Correct 92 ms 119120 KB Output is correct
13 Correct 107 ms 120024 KB Output is correct
14 Correct 108 ms 122964 KB Output is correct
15 Correct 15 ms 102236 KB Output is correct
16 Correct 16 ms 102184 KB Output is correct
17 Correct 16 ms 102236 KB Output is correct
18 Correct 16 ms 102392 KB Output is correct
19 Correct 14 ms 102232 KB Output is correct
20 Incorrect 15 ms 102232 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 101968 KB Output is correct
2 Correct 14 ms 101980 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 102236 KB Output is correct
6 Correct 14 ms 102224 KB Output is correct
7 Correct 14 ms 102236 KB Output is correct
8 Correct 14 ms 102236 KB Output is correct
9 Correct 84 ms 116640 KB Output is correct
10 Correct 103 ms 119460 KB Output is correct
11 Correct 92 ms 119120 KB Output is correct
12 Correct 107 ms 120024 KB Output is correct
13 Correct 108 ms 122964 KB Output is correct
14 Correct 109 ms 116708 KB Output is correct
15 Correct 476 ms 121172 KB Output is correct
16 Correct 463 ms 120656 KB Output is correct
17 Correct 521 ms 121584 KB Output is correct
18 Correct 539 ms 124500 KB Output is correct
19 Correct 563 ms 127064 KB Output is correct
20 Correct 592 ms 128084 KB Output is correct
21 Incorrect 596 ms 127372 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 101976 KB Output is correct
2 Correct 30 ms 101968 KB Output is correct
3 Correct 14 ms 101980 KB Output is correct
4 Correct 14 ms 101980 KB Output is correct
5 Correct 14 ms 101980 KB Output is correct
6 Correct 14 ms 102236 KB Output is correct
7 Correct 14 ms 102224 KB Output is correct
8 Correct 14 ms 102236 KB Output is correct
9 Correct 14 ms 102236 KB Output is correct
10 Correct 84 ms 116640 KB Output is correct
11 Correct 103 ms 119460 KB Output is correct
12 Correct 92 ms 119120 KB Output is correct
13 Correct 107 ms 120024 KB Output is correct
14 Correct 108 ms 122964 KB Output is correct
15 Correct 109 ms 116708 KB Output is correct
16 Correct 476 ms 121172 KB Output is correct
17 Correct 463 ms 120656 KB Output is correct
18 Correct 521 ms 121584 KB Output is correct
19 Correct 539 ms 124500 KB Output is correct
20 Correct 563 ms 127064 KB Output is correct
21 Correct 592 ms 128084 KB Output is correct
22 Incorrect 596 ms 127372 KB Output isn't correct
23 Halted 0 ms 0 KB -