oj.uz

Submission #387768

# Submission time Handle Problem Language Result Execution time Memory
387768 2021-04-09T08:04:40 Z RohamIzadidoost Swapping Cities (APIO20_swap) C++14
0 / 100
 718 ms 524292 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 2000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int par[lg][maxn] , sz[maxn] , mark[maxn] , d[maxn]  , flag , ans , dp[maxn] , mx[lg][maxn] , h[maxn] , mo[maxn];
vec<pair<int , pii>> e ;
vec<pii> adj[maxn] ;
void dfsdown(int v , int p){
	for(auto u : adj[v]){
		if(u.X != p ){
			dfsdown(u.X , v) ;
			dp[v] = min(dp[v] , max(dp[u.X] , u.Y)) ;
		}
	}
}
void dfsup(int v , int p){
	for(auto u : adj[v]){
		if(u.X != p){
			dp[u.X] = min(dp[u.X] , max(u.Y , dp[v]))  ; 
			dfsup(u.X , v) ;
		}
	}
}
void dfs(int v , int p){
	for(auto u : adj[v]){
		if(u.X != p){
			par[0][u.X] = v ; 
			mx[0][u.X] = u.Y ; 
			for(int i = 1 ; i < lg; i ++ ){
				par[i][u.X] = par[i-1][par[i-1][u.X]] ; 
				mx[i][u.X] = max(mx[i-1][u.X] , mx[i-1][par[i-1][u.X]]) ;
			} 
			h[u.X] = h[v] + 1 ; 
			dfs(u.X , v) ;
		}
	}
}
int lca(int u , int v){
	int res = 0 ; 
	if(h[u] > h[v]) swap(u , v) ; 
	for(int i = lg-1 ; i >= 0 ; i -- ){
		if(par[i][v] != -1 && h[par[i][v]] >= h[u]){
			res = max(res , mx[i][v]) ;
			v = par[i][v] ; 
		}
	}
	if(u == v) return res ;
	for(int i = lg -1 ; i >= 0 ; i -- ){
		if(par[i][v] != par[i][u]){
			res = max(res , mx[i][v]) ; 
			res = max(res , mx[i][u]) ; 
			u = par[i][u] ; 
			v = par[i][v] ; 
		}
	}
	res = max(res , par[0][u]) ; res = max(res , par[0][v]) ; 
	return res ; 
}
int getMinimumFuelCapacity(int x , int y){
	if(max(lca(x , y) , dp[x]) == mod)
	return -1 ; 
	else return max(lca(x , y) , dp[x]) ;
}
void init(int n , int m , vec<int> A , vec<int> B , vec<int> W ){
	for(int i = 0 ; i < m ; i ++ ){
		e.pb({W[i] , {A[i] , B[i]}}) ; 
		adj[A[i]].pb({B[i] , W[i]}) ; 
		adj[B[i]].pb({A[i] , W[i]}) ; 
	}
	sort(all(e)) ;
	for(int i = 0 ; i < maxn ; i ++ ){
		dp[i] = mod ;
	}
	for(auto u : e){
		d[u.Y.X] ++ ; 
		d[u.Y.Y] ++ ; 
		if(d[u.Y.X] == 3) dp[u.Y.X] = u.X ; 
		if(d[u.Y.Y] == 3) dp[u.Y.Y] = u.X ; 
	}
	for(auto u : e){
		dp[u.Y.X] = min(dp[u.Y.X] , max(u.X , dp[u.Y.Y])) ; 
		dp[u.Y.Y] = min(dp[u.Y.Y] , max(u.X , dp[u.Y.X])) ; 
	}
	dfsdown(0 , -1) ;
	dfsup(0 , -1) ;  
	h[0] = 1 ; 
	for(int i  = 0 ; i < lg ; i ++ ) par[i][0] = -1 ;
	dfs(0 , -1) ;
}
/*int main()
{
	migmig ;
	int n , m  ; 
	cin>>n>>m ; 
	int u[m] , v[m] , w[m] ;
	for(int i = 0 ; i < m ; i ++ ) cin>>u[i]>>v[i]>>w[i] ; 
	init(n , m , u , v , w) ;
	int q ; 
	cin>>q ; 
	while(q--){
		int U , V ; 
		cin>>U>>V ; 
		cout<<getMinimumFuelCapacity(U , V) << endl ; 
	}
}*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Correct 5 ms 6164 KB Output is correct
6 Correct 5 ms 6224 KB Output is correct
7 Correct 6 ms 6220 KB Output is correct
8 Correct 5 ms 6220 KB Output is correct
9 Correct 188 ms 28728 KB Output is correct
10 Correct 263 ms 35224 KB Output is correct
11 Correct 238 ms 34192 KB Output is correct
12 Correct 249 ms 36112 KB Output is correct
13 Correct 270 ms 38224 KB Output is correct
14 Correct 204 ms 27868 KB Output is correct
15 Correct 718 ms 41152 KB Output is correct
16 Correct 681 ms 38448 KB Output is correct
17 Correct 679 ms 44416 KB Output is correct
18 Correct 661 ms 42848 KB Output is correct
19 Runtime error 487 ms 524292 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Correct 5 ms 6164 KB Output is correct
6 Correct 5 ms 6224 KB Output is correct
7 Correct 6 ms 6220 KB Output is correct
8 Correct 5 ms 6220 KB Output is correct
9 Runtime error 252 ms 524292 KB Execution killed with signal 9

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 524292 KB Execution killed with signal 9

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 5 ms 6092 KB Output is correct
5 Correct 5 ms 6164 KB Output is correct
6 Correct 5 ms 6224 KB Output is correct
7 Correct 6 ms 6220 KB Output is correct
8 Correct 5 ms 6220 KB Output is correct
9 Correct 188 ms 28728 KB Output is correct
10 Correct 263 ms 35224 KB Output is correct
11 Correct 238 ms 34192 KB Output is correct
12 Correct 249 ms 36112 KB Output is correct
13 Correct 270 ms 38224 KB Output is correct
14 Correct 204 ms 27868 KB Output is correct
15 Correct 718 ms 41152 KB Output is correct
16 Correct 681 ms 38448 KB Output is correct
17 Correct 679 ms 44416 KB Output is correct
18 Correct 661 ms 42848 KB Output is correct
19 Incorrect 319 ms 31512 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 524292 KB Execution killed with signal 9