oj.uz

Submission #739678

# Submission time Handle Problem Language Result Execution time Memory
739678 2023-05-11T02:43:12 Z chenyan Swapping Cities (APIO20_swap) C++17
0 / 100
 369 ms 56176 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]});
	}
	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:66:31: warning: unused variable 'j' [-Wunused-variable]
   66 |  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 5400 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5952 KB Output is correct
8 Correct 4 ms 5924 KB Output is correct
9 Correct 66 ms 41656 KB Output is correct
10 Correct 86 ms 51020 KB Output is correct
11 Correct 89 ms 49820 KB Output is correct
12 Correct 95 ms 52792 KB Output is correct
13 Correct 92 ms 54444 KB Output is correct
14 Correct 94 ms 41088 KB Output is correct
15 Correct 351 ms 52820 KB Output is correct
16 Correct 369 ms 50032 KB Output is correct
17 Correct 282 ms 56176 KB Output is correct
18 Correct 353 ms 54804 KB Output is correct
19 Incorrect 77 ms 15820 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 5400 KB Output is correct
3 Incorrect 188 ms 48296 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 5400 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5952 KB Output is correct
8 Correct 4 ms 5924 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 5400 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 4 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 4 ms 5952 KB Output is correct
8 Correct 4 ms 5924 KB Output is correct
9 Correct 66 ms 41656 KB Output is correct
10 Correct 86 ms 51020 KB Output is correct
11 Correct 89 ms 49820 KB Output is correct
12 Correct 95 ms 52792 KB Output is correct
13 Correct 92 ms 54444 KB Output is correct
14 Correct 94 ms 41088 KB Output is correct
15 Correct 351 ms 52820 KB Output is correct
16 Correct 369 ms 50032 KB Output is correct
17 Correct 282 ms 56176 KB Output is correct
18 Correct 353 ms 54804 KB Output is correct
19 Incorrect 188 ms 48296 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 -