oj.uz

Submission #409981

# Submission time Handle Problem Language Result Execution time Memory
409981 2021-05-21T20:09:55 Z MohamedAhmed04 Swapping Cities (APIO20_swap) C++14
6 / 100
 558 ms 63528 KB 
#include <bits/stdc++.h>
#include "swap.h"
//#include "grader.cpp"

using namespace std ;

const int inf = 2e9 ;
const int MAX = 1e5 + 10 ;

int par[MAX] , sz[MAX] , cyc[MAX] ;
vector<int>comp[MAX] ;

int n , m ;

void Init()
{
	for(int i = 1 ; i <= n ; ++i)
		cyc[i] = inf , comp[i].push_back(i) , par[i] = i , sz[i] = 1 ;
}

int root(int node)
{
	if(par[node] == node)
		return node ;
	return (par[node] = root(par[node])) ;
}

void Union(int x , int y , int z)
{
	int a = root(x) ;
	int b = root(y) ;
	if(cyc[a] == inf && cyc[b] != inf)
	{
		for(auto &node : comp[a])
			cyc[node] = z ;
	}
	else if(cyc[a] != inf && cyc[b] == inf)
	{
		for(auto &node : comp[b])
			cyc[node] = z ;
	}
	if(sz[a] < sz[b])
		swap(a , b) ;
	while(comp[b].size())
		comp[a].push_back(comp[b].back()) , comp[b].pop_back() ;
	par[b] = a ;
	sz[a] += sz[b] ;	
}

vector< vector< pair<int , int> > >adj(MAX) ;

int arr2[MAX] , arr3[MAX] , Pval[MAX] , Min[MAX] ;
int P[MAX][20] , Max[MAX][20] , val[MAX][20] , dep[MAX] ;

void dfs(int node , int par , int x , int y)
{
	Pval[node] = x ;
	P[node][0] = par ;
	Max[node][0] = x ;
	val[node][0] = y ;
	for(int i = 1 ; i < 17 ; ++i)
	{
		P[node][i] = P[P[node][i-1]][i-1] ;
		Max[node][i] = max(Max[node][i-1] , Max[P[node][i-1]][i-1]) ;
		val[node][i] = min(val[node][i-1] , val[P[node][i-1]][i-1]) ;
	}
	vector<int>v ;
	for(auto &child : adj[node])
	{
		if(child.first == par)
			continue ;
		v.push_back(child.second) ;
	}
	sort(v.begin() , v.end()) ;
	arr2[node] = arr3[node] = Min[node] = inf ;
	if(v.size() > 1)
		arr2[node] = v[1] ;
	if(v.size() > 2)
		arr3[node] = v[2] , Min[node] = v[2] ;
	for(auto &child : adj[node])
	{
		if(child.first == par)
			continue ;
		dep[child.first] = dep[node] + 1 ;
		dfs(child.first , node , child.second , arr2[node]) ;
		Min[node] = min(Min[node] , max(child.second , Min[child.first])) ;
	}
}

int calc(int x , int y)
{
	if(dep[x] < dep[y])
		swap(x , y) ;
	int a = -inf , b = Min[x] ;
	b = min(cyc[x] , cyc[y]) ;
	for(int i = 16 ; i >= 0 ; --i)
	{
		if((dep[x] - (1 << i)) > dep[y])
		{
			a = max(a , Max[x][i]) ;
			b = min(b , val[x][i]) ;
			x = P[x][i] ;
		}
	}
	if(dep[x] != dep[y])
	{
		if(P[x][0] != y)
			b = min(b , val[x][0]) ;
		a = max(a , Max[x][0]) ;
		x = P[x][0] ;
	}
	if(x == y)
		return max(a , min(b , max(arr2[y] , Pval[y]))) ;
	b = min(b , Min[y]) ;
	for(int i = 16 ; i >= 0 ; --i)
	{
		if(P[x][i] != P[y][i])
		{
			a = max(a , max(Max[x][i] , Max[y][i])) ;
			b = min(b , min(val[x][i] , val[y][i])) ;
			x = P[x][i] , y = P[y][i] ;
		}
	}
	a = max(a , max(Max[x][0] , Max[y][0])) ;
	b = min(b , min(arr3[P[x][0]] , Pval[P[x][0]])) ;
	return max(a , b) ;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

	n = N , m = M ;
	vector< array<int , 3> >v ;
	for(int i = 0 ; i < m ; ++i)
		v.push_back({W[i] , U[i]+1 , V[i]+1}) ;
	Init() ;
	sort(v.begin() , v.end()) ;
	for(auto &a : v)
	{
		int x = a[1] , y = a[2] , z = a[0] ;
		if(root(x) == root(y))
		{
			int r = root(x) ;
			if(cyc[r] == inf)
			{
				for(auto &node : comp[r])
					cyc[node] = z ;
			}
		}
		else
			Union(x , y , z) , adj[x].emplace_back(y , z) , adj[y].emplace_back(x , z) ;
	}
	dfs(1 , 0 , inf , inf) ;
}

int getMinimumFuelCapacity(int x, int y) 
{
	x++ , y++ ;
	int ans = calc(x , y) ;
	if(ans == inf)
		ans = -1 ;
	return ans ;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5416 KB Output is correct
6 Correct 4 ms 5408 KB Output is correct
7 Correct 5 ms 5548 KB Output is correct
8 Correct 5 ms 5548 KB Output is correct
9 Correct 168 ms 44576 KB Output is correct
10 Correct 223 ms 55852 KB Output is correct
11 Correct 215 ms 53976 KB Output is correct
12 Correct 236 ms 57244 KB Output is correct
13 Correct 203 ms 58800 KB Output is correct
14 Correct 200 ms 43320 KB Output is correct
15 Correct 510 ms 58124 KB Output is correct
16 Correct 511 ms 53592 KB Output is correct
17 Correct 497 ms 63528 KB Output is correct
18 Correct 481 ms 58708 KB Output is correct
19 Correct 117 ms 18160 KB Output is correct
20 Correct 500 ms 57752 KB Output is correct
21 Correct 540 ms 54296 KB Output is correct
22 Correct 558 ms 59576 KB Output is correct
23 Correct 529 ms 58360 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Incorrect 244 ms 44892 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 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5416 KB Output is correct
6 Correct 4 ms 5408 KB Output is correct
7 Correct 5 ms 5548 KB Output is correct
8 Correct 5 ms 5548 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 4 ms 5452 KB Output is correct
11 Correct 4 ms 5452 KB Output is correct
12 Correct 4 ms 5452 KB Output is correct
13 Correct 4 ms 5324 KB Output is correct
14 Correct 5 ms 5400 KB Output is correct
15 Incorrect 5 ms 5416 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5416 KB Output is correct
7 Correct 4 ms 5408 KB Output is correct
8 Correct 5 ms 5548 KB Output is correct
9 Correct 5 ms 5548 KB Output is correct
10 Correct 168 ms 44576 KB Output is correct
11 Correct 223 ms 55852 KB Output is correct
12 Correct 215 ms 53976 KB Output is correct
13 Correct 236 ms 57244 KB Output is correct
14 Correct 203 ms 58800 KB Output is correct
15 Correct 4 ms 5452 KB Output is correct
16 Correct 4 ms 5452 KB Output is correct
17 Correct 4 ms 5452 KB Output is correct
18 Correct 4 ms 5324 KB Output is correct
19 Correct 5 ms 5400 KB Output is correct
20 Incorrect 5 ms 5416 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5416 KB Output is correct
6 Correct 4 ms 5408 KB Output is correct
7 Correct 5 ms 5548 KB Output is correct
8 Correct 5 ms 5548 KB Output is correct
9 Correct 168 ms 44576 KB Output is correct
10 Correct 223 ms 55852 KB Output is correct
11 Correct 215 ms 53976 KB Output is correct
12 Correct 236 ms 57244 KB Output is correct
13 Correct 203 ms 58800 KB Output is correct
14 Correct 200 ms 43320 KB Output is correct
15 Correct 510 ms 58124 KB Output is correct
16 Correct 511 ms 53592 KB Output is correct
17 Correct 497 ms 63528 KB Output is correct
18 Correct 481 ms 58708 KB Output is correct
19 Incorrect 244 ms 44892 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5416 KB Output is correct
7 Correct 4 ms 5408 KB Output is correct
8 Correct 5 ms 5548 KB Output is correct
9 Correct 5 ms 5548 KB Output is correct
10 Correct 168 ms 44576 KB Output is correct
11 Correct 223 ms 55852 KB Output is correct
12 Correct 215 ms 53976 KB Output is correct
13 Correct 236 ms 57244 KB Output is correct
14 Correct 203 ms 58800 KB Output is correct
15 Correct 200 ms 43320 KB Output is correct
16 Correct 510 ms 58124 KB Output is correct
17 Correct 511 ms 53592 KB Output is correct
18 Correct 497 ms 63528 KB Output is correct
19 Correct 481 ms 58708 KB Output is correct
20 Incorrect 244 ms 44892 KB Output isn't correct
21 Halted 0 ms 0 KB -