oj.uz

Submission #410002

# Submission time Handle Problem Language Result Execution time Memory
410002 2021-05-21T20:56:57 Z MohamedAhmed04 Swapping Cities (APIO20_swap) C++14
13 / 100
 434 ms 44600 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] ;
int val[MAX] ;
vector<int>comp[MAX] ;

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

int n , m ;

void Init()
{
	for(int i = 1 ; i <= n ; ++i)
		cyc[i] = val[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(val[a] == inf && val[b] != inf)
	{
		for(auto &node : comp[a])
			val[node] = z ;
	}
	if(val[a] != inf && val[b] == inf)
	{
		for(auto &node : comp[b])
			val[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() ;
	if(adj[x].size() == 2 || adj[y].size() == 2)
	{
		for(auto &node : comp[a])
			val[node] = z ;	
	}
	par[b] = a ;
	sz[a] += sz[b] ;	
}

int P[MAX][20] , Max[MAX][20] , dep[MAX] ;

void dfs(int node , int par , int x)
{
	P[node][0] = par ;
	Max[node][0] = x ;
	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]) ;
	}
	for(auto &child : adj[node])
	{
		if(child.first == par)
			continue ;
		dep[child.first] = dep[node] + 1 ;
		dfs(child.first , node , child.second) ;
	}
}

int calc(int x , int y)
{
	if(dep[x] < dep[y])
		swap(x , y) ;
	int a = -inf ;
	int b = min({val[x] , val[y] , cyc[x] , cyc[y]}) ;
	for(int i = 16 ; i >= 0 ; --i)
	{
		if((dep[x] - (1 << i)) >= dep[y])
		{
			a = max(a , Max[x][i]) ;
			x = P[x][i] ;
		}
	}
	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])) ;
			x = P[x][i] , y = P[y][i] ;
		}
	}
	a = max(a , max(Max[x][0] , Max[y][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) ;
}

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 5012 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 5 ms 5360 KB Output is correct
8 Correct 4 ms 5280 KB Output is correct
9 Correct 138 ms 33248 KB Output is correct
10 Correct 185 ms 40120 KB Output is correct
11 Correct 185 ms 39248 KB Output is correct
12 Correct 191 ms 41316 KB Output is correct
13 Correct 165 ms 40064 KB Output is correct
14 Correct 169 ms 32824 KB Output is correct
15 Correct 405 ms 42152 KB Output is correct
16 Correct 404 ms 39664 KB Output is correct
17 Correct 421 ms 44600 KB Output is correct
18 Correct 388 ms 40720 KB Output is correct
19 Correct 107 ms 14744 KB Output is correct
20 Correct 401 ms 41948 KB Output is correct
21 Correct 434 ms 40284 KB Output is correct
22 Correct 423 ms 43652 KB Output is correct
23 Correct 394 ms 41220 KB Output is correct

Subtask #2
7.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 Correct 225 ms 34640 KB Output is correct
4 Correct 228 ms 36232 KB Output is correct
5 Correct 235 ms 35684 KB Output is correct
6 Correct 228 ms 36108 KB Output is correct
7 Correct 240 ms 36000 KB Output is correct
8 Correct 232 ms 34840 KB Output is correct
9 Correct 226 ms 35796 KB Output is correct
10 Correct 230 ms 34672 KB Output is correct

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 5012 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 5 ms 5360 KB Output is correct
8 Correct 4 ms 5280 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Incorrect 4 ms 5324 KB Output isn't correct
11 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 5012 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 5 ms 5360 KB Output is correct
9 Correct 4 ms 5280 KB Output is correct
10 Correct 138 ms 33248 KB Output is correct
11 Correct 185 ms 40120 KB Output is correct
12 Correct 185 ms 39248 KB Output is correct
13 Correct 191 ms 41316 KB Output is correct
14 Correct 165 ms 40064 KB Output is correct
15 Incorrect 4 ms 5324 KB Output isn't correct
16 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 5012 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 5 ms 5360 KB Output is correct
8 Correct 4 ms 5280 KB Output is correct
9 Correct 138 ms 33248 KB Output is correct
10 Correct 185 ms 40120 KB Output is correct
11 Correct 185 ms 39248 KB Output is correct
12 Correct 191 ms 41316 KB Output is correct
13 Correct 165 ms 40064 KB Output is correct
14 Correct 169 ms 32824 KB Output is correct
15 Correct 405 ms 42152 KB Output is correct
16 Correct 404 ms 39664 KB Output is correct
17 Correct 421 ms 44600 KB Output is correct
18 Correct 388 ms 40720 KB Output is correct
19 Correct 225 ms 34640 KB Output is correct
20 Correct 228 ms 36232 KB Output is correct
21 Correct 235 ms 35684 KB Output is correct
22 Correct 228 ms 36108 KB Output is correct
23 Correct 240 ms 36000 KB Output is correct
24 Correct 232 ms 34840 KB Output is correct
25 Correct 226 ms 35796 KB Output is correct
26 Correct 230 ms 34672 KB Output is correct
27 Incorrect 4 ms 5324 KB Output isn't correct
28 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 5012 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 5 ms 5360 KB Output is correct
9 Correct 4 ms 5280 KB Output is correct
10 Correct 138 ms 33248 KB Output is correct
11 Correct 185 ms 40120 KB Output is correct
12 Correct 185 ms 39248 KB Output is correct
13 Correct 191 ms 41316 KB Output is correct
14 Correct 165 ms 40064 KB Output is correct
15 Correct 169 ms 32824 KB Output is correct
16 Correct 405 ms 42152 KB Output is correct
17 Correct 404 ms 39664 KB Output is correct
18 Correct 421 ms 44600 KB Output is correct
19 Correct 388 ms 40720 KB Output is correct
20 Correct 225 ms 34640 KB Output is correct
21 Correct 228 ms 36232 KB Output is correct
22 Correct 235 ms 35684 KB Output is correct
23 Correct 228 ms 36108 KB Output is correct
24 Correct 240 ms 36000 KB Output is correct
25 Correct 232 ms 34840 KB Output is correct
26 Correct 226 ms 35796 KB Output is correct
27 Correct 230 ms 34672 KB Output is correct
28 Incorrect 4 ms 5324 KB Output isn't correct
29 Halted 0 ms 0 KB -