oj.uz

답안 #206550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206550 2020-03-04T00:07:30 Z MohamedAhmed04 Mag (COCI16_mag) C++14
84 / 120
 557 ms 144120 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

int arr[MAX] , dpdown[MAX] , dpup[MAX] ;
int n ;

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

int Max = 0 ;

void dfs(int node , int par)
{
	if(arr[node] == 1)
		dpdown[node] = 1 ;
	else
		dpdown[node] = 0 ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , node) ;
		if(dpdown[node])
			dpdown[node] = max(dpdown[node] , dpdown[child]+1) ;
	}
	Max = max(Max , dpdown[node]) ;
}

bool flag = false ;

void dfs2(int node , int par)
{
	int cnt = 0 ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs2(child , node) ;
		if(arr[node] == 2)
			cnt += (dpdown[child] == Max) ;
	}
	if(cnt > 1)
		flag = true ;
	return ;
}

void dfs3(int node , int par , int best)
{
	dpup[node] = best + 1 ;
	if(arr[node] != 1)
	{
		dpup[node] = 0 ;
		for(auto &child : adj[node])
		{
			if(child == par)
				continue ;
			dfs3(child , node , 0) ;
		}
		if(arr[node] == 2)
		{
			for(auto &child : adj[node])
			{
				if(child == par)
					continue ;
				if(dpdown[child] == Max && best == Max)
					flag = true ;
			}
		}
		return ;
	}
	int mx = dpup[node] , c = node ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		if(dpdown[child]+1 > mx)
			mx = dpdown[child]+1 , c = child ;
	}
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		if(c != child)
			dfs3(child , node , mx) ;
		else
		{
			int mx2 = dpup[node] , c = node ;
			for(auto &child2 : adj[node])
			{
				if(child2 == par || child == child2)
					continue ;
				if(dpdown[child2]+1 > mx2)
					mx2 = dpdown[child2]+1 , c = child2 ;
			}
			dfs3(child , node , mx2) ;
		}
	}
	return ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n-1 ;  ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	int cnt = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>arr[i] ;
		cnt += (arr[i] == 1) ;
	}
	if(!cnt)
		return cout<<*min_element(arr+1 , arr+n+1)<<"/"<<1<<"\n" , 0 ;
	dfs(1 , -1) ;
	int ans = Max ;
	dfs2(1 , -1) ;
	dfs3(1 , -1 , 0) ;
	if(flag == true)
		return cout<<2<<"/"<<ans*2+1<<"\n" , 0 ;
	else
		return cout<<1<<"/"<<ans<<"\n" , 0 ;
}

Compilation message

mag.cpp: In function 'void dfs3(int, int, int)':
mag.cpp:89:27: warning: variable 'c' set but not used [-Wunused-but-set-variable]
    int mx2 = dpup[node] , c = node ;
                           ^

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23928 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23928 KB Output is correct
2 Correct 18 ms 23800 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 433 ms 89796 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23800 KB Output is correct
2 Correct 557 ms 144120 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 541 ms 142328 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 469 ms 66808 KB Output is correct
2 Correct 332 ms 55544 KB Output is correct

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 432 ms 67816 KB Output is correct
2 Incorrect 87 ms 28280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 28152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 407 ms 64472 KB Output is correct
2 Correct 447 ms 66132 KB Output is correct

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 466 ms 67448 KB Output is correct
2 Incorrect 368 ms 45944 KB Output isn't correct