oj.uz

답안 #410011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410011 2021-05-21T21:04:37 Z MohamedAhmed04 자매 도시 (APIO20_swap) C++14
13 / 100
 500 ms 45096 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({max(val[x] , val[y]) , max(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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 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 5 ms 5288 KB Output is correct
7 Correct 5 ms 5324 KB Output is correct
8 Correct 4 ms 5284 KB Output is correct
9 Correct 145 ms 33452 KB Output is correct
10 Correct 229 ms 40408 KB Output is correct
11 Correct 194 ms 39456 KB Output is correct
12 Correct 202 ms 41784 KB Output is correct
13 Correct 170 ms 40552 KB Output is correct
14 Correct 202 ms 32956 KB Output is correct
15 Correct 500 ms 42708 KB Output is correct
16 Correct 496 ms 40248 KB Output is correct
17 Correct 454 ms 45096 KB Output is correct
18 Correct 456 ms 41152 KB Output is correct
19 Correct 111 ms 15048 KB Output is correct
20 Correct 447 ms 42172 KB Output is correct
21 Correct 427 ms 40408 KB Output is correct
22 Correct 500 ms 43680 KB Output is correct
23 Correct 439 ms 41160 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 KB Output is correct
3 Correct 231 ms 35332 KB Output is correct
4 Correct 242 ms 36560 KB Output is correct
5 Correct 249 ms 36068 KB Output is correct
6 Correct 236 ms 36392 KB Output is correct
7 Correct 252 ms 36488 KB Output is correct
8 Correct 233 ms 35100 KB Output is correct
9 Correct 249 ms 36000 KB Output is correct
10 Correct 266 ms 34932 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 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 5 ms 5288 KB Output is correct
7 Correct 5 ms 5324 KB Output is correct
8 Correct 4 ms 5284 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Incorrect 5 ms 5284 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5016 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 5 ms 5288 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 4 ms 5284 KB Output is correct
10 Correct 145 ms 33452 KB Output is correct
11 Correct 229 ms 40408 KB Output is correct
12 Correct 194 ms 39456 KB Output is correct
13 Correct 202 ms 41784 KB Output is correct
14 Correct 170 ms 40552 KB Output is correct
15 Incorrect 5 ms 5284 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5016 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 5 ms 5288 KB Output is correct
7 Correct 5 ms 5324 KB Output is correct
8 Correct 4 ms 5284 KB Output is correct
9 Correct 145 ms 33452 KB Output is correct
10 Correct 229 ms 40408 KB Output is correct
11 Correct 194 ms 39456 KB Output is correct
12 Correct 202 ms 41784 KB Output is correct
13 Correct 170 ms 40552 KB Output is correct
14 Correct 202 ms 32956 KB Output is correct
15 Correct 500 ms 42708 KB Output is correct
16 Correct 496 ms 40248 KB Output is correct
17 Correct 454 ms 45096 KB Output is correct
18 Correct 456 ms 41152 KB Output is correct
19 Correct 231 ms 35332 KB Output is correct
20 Correct 242 ms 36560 KB Output is correct
21 Correct 249 ms 36068 KB Output is correct
22 Correct 236 ms 36392 KB Output is correct
23 Correct 252 ms 36488 KB Output is correct
24 Correct 233 ms 35100 KB Output is correct
25 Correct 249 ms 36000 KB Output is correct
26 Correct 266 ms 34932 KB Output is correct
27 Incorrect 5 ms 5284 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5016 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 5 ms 5288 KB Output is correct
8 Correct 5 ms 5324 KB Output is correct
9 Correct 4 ms 5284 KB Output is correct
10 Correct 145 ms 33452 KB Output is correct
11 Correct 229 ms 40408 KB Output is correct
12 Correct 194 ms 39456 KB Output is correct
13 Correct 202 ms 41784 KB Output is correct
14 Correct 170 ms 40552 KB Output is correct
15 Correct 202 ms 32956 KB Output is correct
16 Correct 500 ms 42708 KB Output is correct
17 Correct 496 ms 40248 KB Output is correct
18 Correct 454 ms 45096 KB Output is correct
19 Correct 456 ms 41152 KB Output is correct
20 Correct 231 ms 35332 KB Output is correct
21 Correct 242 ms 36560 KB Output is correct
22 Correct 249 ms 36068 KB Output is correct
23 Correct 236 ms 36392 KB Output is correct
24 Correct 252 ms 36488 KB Output is correct
25 Correct 233 ms 35100 KB Output is correct
26 Correct 249 ms 36000 KB Output is correct
27 Correct 266 ms 34932 KB Output is correct
28 Incorrect 5 ms 5284 KB Output isn't correct
29 Halted 0 ms 0 KB -