oj.uz

답안 #739680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739680 2023-05-11T03:07:01 Z chenyan 자매 도시 (APIO20_swap) C++17
0 / 100
 407 ms 55984 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;
	dp[0][0]=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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 3 ms 5844 KB Output is correct
8 Correct 3 ms 5988 KB Output is correct
9 Correct 72 ms 41528 KB Output is correct
10 Correct 86 ms 50752 KB Output is correct
11 Correct 91 ms 49484 KB Output is correct
12 Correct 87 ms 52428 KB Output is correct
13 Correct 93 ms 54312 KB Output is correct
14 Correct 103 ms 40884 KB Output is correct
15 Correct 378 ms 52540 KB Output is correct
16 Correct 407 ms 49780 KB Output is correct
17 Correct 316 ms 55984 KB Output is correct
18 Correct 370 ms 54604 KB Output is correct
19 Incorrect 86 ms 15536 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Incorrect 180 ms 48012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 3 ms 5844 KB Output is correct
8 Correct 3 ms 5988 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5844 KB Output is correct
6 Correct 5 ms 5844 KB Output is correct
7 Correct 3 ms 5844 KB Output is correct
8 Correct 3 ms 5988 KB Output is correct
9 Correct 72 ms 41528 KB Output is correct
10 Correct 86 ms 50752 KB Output is correct
11 Correct 91 ms 49484 KB Output is correct
12 Correct 87 ms 52428 KB Output is correct
13 Correct 93 ms 54312 KB Output is correct
14 Correct 103 ms 40884 KB Output is correct
15 Correct 378 ms 52540 KB Output is correct
16 Correct 407 ms 49780 KB Output is correct
17 Correct 316 ms 55984 KB Output is correct
18 Correct 370 ms 54604 KB Output is correct
19 Incorrect 180 ms 48012 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -