oj.uz

Submission #739711

# Submission time Handle Problem Language Result Execution time Memory
739711 2023-05-11T05:40:30 Z chenyan Swapping Cities (APIO20_swap) C++17
0 / 100
 405 ms 57100 KB 
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define pii pair<int,int>
#define pdd pair<ld,ld>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define fastio ios::sync_with_stdio(0),cin.tie(0);
#define nl '\n'
#define mN 200010
int dep[mN],n,m,fa[31][mN],dp[31][mN],st[31][mN];
vector<pii>g[mN];
bitset<mN>vis;
void dfs(int v){
	vis[v]=1;
	pii a,b;
	a.ff=b.ff=-1;
	a.ss=b.ss=2e9;
	for(auto[u,w]:g[v]){
		if(vis[u])continue;
		if(a.ff==-1||a.ss>w){
			b=a;
			a.ff=u;
			a.ss=w;
		}
		else if(b.ff==-1||b.ss>w){
			b.ff=u;
			b.ss=w;
		}
	}
	for(auto[u,w]:g[v]){
		if(vis[u])continue;
		dep[u]=dep[v]+1;
		fa[0][u]=v;
		if(a.ff!=u)dp[0][u]=a.ss;
		else dp[0][u]=b.ss;
		st[0][u]=w;
		dfs(u);
	}
}
void init(int NN,int M,vector<int>u,vector<int>v,vector<int>w){
	int i,j;
	n=NN,m=M;
	for(int i=0;i<m;i++){
		g[u[i]].pb({v[i],w[i]});
		g[v[i]].pb({u[i],w[i]});
	}
	fa[0][0]=mN-1;
	for(i=0;i<30;i++)dp[i][0]=2e9,dp[i][mN-1]=2e9;
	for(i=0;i<n;i++)dp[0][i]=2e9;
	for(i=0;i<n;i++)sort(all(g[i]),[](pii a,pii b){return a.ss<b.ss;});
	dfs(0);
	for(i=1;i<30;i++){
		for(j=0;j<n;j++){
			fa[i][j]=fa[i-1][fa[i-1][j]];
			st[i][j]=max(st[i-1][j],st[i-1][fa[i-1][j]]);
			dp[i][j]=min(dp[i-1][j],dp[i-1][fa[i-1][j]]);
		}
	}
}
int getMinimumFuelCapacity(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	int d=dep[u]-dep[v],mi=2e9,i,j,ans=0;
	for(i=0;i<30;i++){
		if(!d)break;
		if((1<<i)&(d-1)){
			ans=max(ans,st[i][u]);
			mi=min(mi,dp[i][u]);
			u=fa[i][u];
		}
	}
	if(d){
		ans=max(ans,st[0][u]);
		if(fa[0][u]!=v)mi=min(mi,dp[0][u]);
		u=fa[0][u];
	}
	if(u==v){
		ans=max(ans,mi);
		return (ans==2e9?-1:ans);
	}
	for(i=29;i>=0;i--){
		while(fa[i][u]!=fa[i][v]){
			ans=max({ans,st[i][u],st[i][v]});
			mi=min({mi,dp[i][u],dp[i][v]});
			u=fa[i][u];
			v=fa[i][v];
		}
	}
	ans=max({ans,st[0][u],st[0][v]});
	for(auto[f,w]:g[fa[0][u]]){
		if(f!=u&&f!=v){
			mi=min(w,mi);
			break;
		}
	}
	ans=max(ans,mi);
	return (ans==2e9?-1:ans);
}
/*
8 7
0 1 1
1 2 5
1 3 2
0 4 3
4 5 6
4 6 4
4 7 5
5
5 7
3 7
2 4
2 3
1 6
signed main(){
	fastio;
}
*/

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:68:31: warning: unused variable 'j' [-Wunused-variable]
   68 |  int d=dep[u]-dep[v],mi=2e9,i,j,ans=0;
      |                               ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5404 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5920 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 76 ms 42596 KB Output is correct
10 Correct 88 ms 51940 KB Output is correct
11 Correct 89 ms 50608 KB Output is correct
12 Correct 90 ms 53568 KB Output is correct
13 Correct 93 ms 55320 KB Output is correct
14 Correct 104 ms 41972 KB Output is correct
15 Correct 377 ms 53716 KB Output is correct
16 Correct 405 ms 50960 KB Output is correct
17 Correct 293 ms 57100 KB Output is correct
18 Correct 376 ms 55708 KB Output is correct
19 Incorrect 82 ms 16668 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Incorrect 187 ms 49180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5404 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5920 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Incorrect 3 ms 5460 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5404 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 4 ms 5844 KB Output is correct
7 Correct 4 ms 5920 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 76 ms 42596 KB Output is correct
10 Correct 88 ms 51940 KB Output is correct
11 Correct 89 ms 50608 KB Output is correct
12 Correct 90 ms 53568 KB Output is correct
13 Correct 93 ms 55320 KB Output is correct
14 Correct 104 ms 41972 KB Output is correct
15 Correct 377 ms 53716 KB Output is correct
16 Correct 405 ms 50960 KB Output is correct
17 Correct 293 ms 57100 KB Output is correct
18 Correct 376 ms 55708 KB Output is correct
19 Incorrect 187 ms 49180 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -