oj.uz

Submission #409944

# Submission time Handle Problem Language Result Execution time Memory
409944 2021-05-21T19:35:57 Z MohamedAhmed04 Swapping Cities (APIO20_swap) C++14
6 / 100
 563 ms 58308 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] = x ;
	if(v.size() > 2)
		arr[node] = min(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 5456 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5432 KB Output is correct
9 Correct 174 ms 41528 KB Output is correct
10 Correct 229 ms 52080 KB Output is correct
11 Correct 222 ms 50272 KB Output is correct
12 Correct 236 ms 53560 KB Output is correct
13 Correct 200 ms 54560 KB Output is correct
14 Correct 205 ms 40320 KB Output is correct
15 Correct 526 ms 53372 KB Output is correct
16 Correct 551 ms 49232 KB Output is correct
17 Correct 500 ms 58308 KB Output is correct
18 Correct 489 ms 53660 KB Output is correct
19 Correct 143 ms 16304 KB Output is correct
20 Correct 527 ms 52360 KB Output is correct
21 Correct 538 ms 49364 KB Output is correct
22 Correct 563 ms 54168 KB Output is correct
23 Correct 504 ms 52820 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 234 ms 41824 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 5456 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5432 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 5 ms 5324 KB Output is correct
11 Correct 5 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 5 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 5456 KB Output is correct
7 Correct 5 ms 5416 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 4 ms 5432 KB Output is correct
10 Correct 174 ms 41528 KB Output is correct
11 Correct 229 ms 52080 KB Output is correct
12 Correct 222 ms 50272 KB Output is correct
13 Correct 236 ms 53560 KB Output is correct
14 Correct 200 ms 54560 KB Output is correct
15 Correct 5 ms 5324 KB Output is correct
16 Correct 5 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 5 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 5456 KB Output is correct
6 Correct 5 ms 5416 KB Output is correct
7 Correct 4 ms 5452 KB Output is correct
8 Correct 4 ms 5432 KB Output is correct
9 Correct 174 ms 41528 KB Output is correct
10 Correct 229 ms 52080 KB Output is correct
11 Correct 222 ms 50272 KB Output is correct
12 Correct 236 ms 53560 KB Output is correct
13 Correct 200 ms 54560 KB Output is correct
14 Correct 205 ms 40320 KB Output is correct
15 Correct 526 ms 53372 KB Output is correct
16 Correct 551 ms 49232 KB Output is correct
17 Correct 500 ms 58308 KB Output is correct
18 Correct 489 ms 53660 KB Output is correct
19 Incorrect 234 ms 41824 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 5456 KB Output is correct
7 Correct 5 ms 5416 KB Output is correct
8 Correct 4 ms 5452 KB Output is correct
9 Correct 4 ms 5432 KB Output is correct
10 Correct 174 ms 41528 KB Output is correct
11 Correct 229 ms 52080 KB Output is correct
12 Correct 222 ms 50272 KB Output is correct
13 Correct 236 ms 53560 KB Output is correct
14 Correct 200 ms 54560 KB Output is correct
15 Correct 205 ms 40320 KB Output is correct
16 Correct 526 ms 53372 KB Output is correct
17 Correct 551 ms 49232 KB Output is correct
18 Correct 500 ms 58308 KB Output is correct
19 Correct 489 ms 53660 KB Output is correct
20 Incorrect 234 ms 41824 KB Output isn't correct
21 Halted 0 ms 0 KB -