oj.uz

Submission #409938

# Submission time Handle Problem Language Result Execution time Memory
409938 2021-05-21T19:30:45 Z MohamedAhmed04 Swapping Cities (APIO20_swap) C++14
6 / 100
 522 ms 58400 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 arr[MAX] ;
int P[MAX][20] , Max[MAX][20] , val[MAX][20] , dep[MAX] ;

void dfs(int node , int par , int x , int y)
{
	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()) ;
	int b = inf ;
	if(v.size() > 1)
		b = v[1] ;
	arr[node] = inf ;
	if(v.size() > 2)
		arr[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 , b) ;
	}
}

int calc(int x , int y)
{
	if(dep[x] < dep[y])
		swap(x , y) ;
	int a = -inf , b = inf ;
	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 , b) ;
	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 , arr[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 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5396 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 159 ms 41504 KB Output is correct
10 Correct 223 ms 52080 KB Output is correct
11 Correct 206 ms 50404 KB Output is correct
12 Correct 228 ms 53536 KB Output is correct
13 Correct 191 ms 54596 KB Output is correct
14 Correct 193 ms 40356 KB Output is correct
15 Correct 490 ms 53368 KB Output is correct
16 Correct 496 ms 49224 KB Output is correct
17 Correct 483 ms 58400 KB Output is correct
18 Correct 458 ms 53668 KB Output is correct
19 Correct 114 ms 16348 KB Output is correct
20 Correct 476 ms 52320 KB Output is correct
21 Correct 506 ms 49360 KB Output is correct
22 Correct 522 ms 54176 KB Output is correct
23 Correct 477 ms 52892 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 226 ms 41812 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 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5396 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 4 ms 5452 KB Output is correct
12 Correct 5 ms 5324 KB Output is correct
13 Correct 4 ms 5324 KB Output is correct
14 Correct 4 ms 5324 KB Output is correct
15 Incorrect 5 ms 5452 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 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5396 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 159 ms 41504 KB Output is correct
11 Correct 223 ms 52080 KB Output is correct
12 Correct 206 ms 50404 KB Output is correct
13 Correct 228 ms 53536 KB Output is correct
14 Correct 191 ms 54596 KB Output is correct
15 Correct 4 ms 5324 KB Output is correct
16 Correct 4 ms 5452 KB Output is correct
17 Correct 5 ms 5324 KB Output is correct
18 Correct 4 ms 5324 KB Output is correct
19 Correct 4 ms 5324 KB Output is correct
20 Incorrect 5 ms 5452 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 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5452 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5396 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 159 ms 41504 KB Output is correct
10 Correct 223 ms 52080 KB Output is correct
11 Correct 206 ms 50404 KB Output is correct
12 Correct 228 ms 53536 KB Output is correct
13 Correct 191 ms 54596 KB Output is correct
14 Correct 193 ms 40356 KB Output is correct
15 Correct 490 ms 53368 KB Output is correct
16 Correct 496 ms 49224 KB Output is correct
17 Correct 483 ms 58400 KB Output is correct
18 Correct 458 ms 53668 KB Output is correct
19 Incorrect 226 ms 41812 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 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5396 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 159 ms 41504 KB Output is correct
11 Correct 223 ms 52080 KB Output is correct
12 Correct 206 ms 50404 KB Output is correct
13 Correct 228 ms 53536 KB Output is correct
14 Correct 191 ms 54596 KB Output is correct
15 Correct 193 ms 40356 KB Output is correct
16 Correct 490 ms 53368 KB Output is correct
17 Correct 496 ms 49224 KB Output is correct
18 Correct 483 ms 58400 KB Output is correct
19 Correct 458 ms 53668 KB Output is correct
20 Incorrect 226 ms 41812 KB Output isn't correct
21 Halted 0 ms 0 KB -