oj.uz

Submission #897100

# Submission time Handle Problem Language Result Execution time Memory
897100 2024-01-02T14:38:36 Z LCJLY Swapping Cities (APIO20_swap) C++14
0 / 100
 212 ms 82088 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 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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 56924 KB Output is correct
2 Correct 8 ms 56924 KB Output is correct
3 Correct 8 ms 56924 KB Output is correct
4 Correct 9 ms 56920 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 9 ms 57168 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 68216 KB Output is correct
10 Correct 85 ms 70228 KB Output is correct
11 Correct 86 ms 70224 KB Output is correct
12 Correct 84 ms 70736 KB Output is correct
13 Correct 95 ms 74572 KB Output is correct
14 Correct 74 ms 68380 KB Output is correct
15 Correct 155 ms 72100 KB Output is correct
16 Correct 179 ms 71768 KB Output is correct
17 Correct 165 ms 72336 KB Output is correct
18 Correct 212 ms 76384 KB Output is correct
19 Incorrect 73 ms 64440 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 56924 KB Output is correct
2 Correct 8 ms 56924 KB Output is correct
3 Correct 172 ms 81264 KB Output is correct
4 Correct 181 ms 82088 KB Output is correct
5 Incorrect 174 ms 81656 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 56924 KB Output is correct
2 Correct 8 ms 56924 KB Output is correct
3 Correct 8 ms 56924 KB Output is correct
4 Correct 9 ms 56920 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 9 ms 57168 KB Output is correct
7 Correct 9 ms 59228 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 59220 KB Output is correct
11 Correct 10 ms 59228 KB Output is correct
12 Correct 9 ms 59228 KB Output is correct
13 Correct 9 ms 57040 KB Output is correct
14 Correct 9 ms 57180 KB Output is correct
15 Incorrect 11 ms 59288 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56924 KB Output is correct
2 Correct 13 ms 56924 KB Output is correct
3 Correct 8 ms 56924 KB Output is correct
4 Correct 8 ms 56924 KB Output is correct
5 Correct 9 ms 56920 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57168 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 68216 KB Output is correct
11 Correct 85 ms 70228 KB Output is correct
12 Correct 86 ms 70224 KB Output is correct
13 Correct 84 ms 70736 KB Output is correct
14 Correct 95 ms 74572 KB Output is correct
15 Correct 9 ms 59220 KB Output is correct
16 Correct 10 ms 59228 KB Output is correct
17 Correct 9 ms 59228 KB Output is correct
18 Correct 9 ms 57040 KB Output is correct
19 Correct 9 ms 57180 KB Output is correct
20 Incorrect 11 ms 59288 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 56924 KB Output is correct
2 Correct 8 ms 56924 KB Output is correct
3 Correct 8 ms 56924 KB Output is correct
4 Correct 9 ms 56920 KB Output is correct
5 Correct 9 ms 57180 KB Output is correct
6 Correct 9 ms 57168 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 68216 KB Output is correct
10 Correct 85 ms 70228 KB Output is correct
11 Correct 86 ms 70224 KB Output is correct
12 Correct 84 ms 70736 KB Output is correct
13 Correct 95 ms 74572 KB Output is correct
14 Correct 74 ms 68380 KB Output is correct
15 Correct 155 ms 72100 KB Output is correct
16 Correct 179 ms 71768 KB Output is correct
17 Correct 165 ms 72336 KB Output is correct
18 Correct 212 ms 76384 KB Output is correct
19 Correct 172 ms 81264 KB Output is correct
20 Correct 181 ms 82088 KB Output is correct
21 Incorrect 174 ms 81656 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 56924 KB Output is correct
2 Correct 13 ms 56924 KB Output is correct
3 Correct 8 ms 56924 KB Output is correct
4 Correct 8 ms 56924 KB Output is correct
5 Correct 9 ms 56920 KB Output is correct
6 Correct 9 ms 57180 KB Output is correct
7 Correct 9 ms 57168 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 68216 KB Output is correct
11 Correct 85 ms 70228 KB Output is correct
12 Correct 86 ms 70224 KB Output is correct
13 Correct 84 ms 70736 KB Output is correct
14 Correct 95 ms 74572 KB Output is correct
15 Correct 74 ms 68380 KB Output is correct
16 Correct 155 ms 72100 KB Output is correct
17 Correct 179 ms 71768 KB Output is correct
18 Correct 165 ms 72336 KB Output is correct
19 Correct 212 ms 76384 KB Output is correct
20 Correct 172 ms 81264 KB Output is correct
21 Correct 181 ms 82088 KB Output is correct
22 Incorrect 174 ms 81656 KB Output isn't correct
23 Halted 0 ms 0 KB -