oj.uz

Submission #256451

# Submission time Handle Problem Language Result Execution time Memory
256451 2020-08-02T17:36:00 Z ElyesChaabouni Mag (COCI16_mag) C++14
0 / 120
 722 ms 97272 KB 
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000001
#define PI 3.14159265358979323846
using namespace std;
vector<pair<int, int> >v[1000005];
int a[1000005];
pair<long long, long long>mi(pair<long long, long long>x, pair<long long , long long>y)
{
	if(x.first*y.second <= y.first*x.second)
		return x;
	return y;
}
int dfs(int idx, int anc)
{
	if(a[idx]!=1)
		return 0;
	int cu=0;
	for(int i = 0; i < v[idx].size(); i++)
	{
		if(v[idx][i].first!=anc)
		{
			if(v[idx][i].second==-1)
				v[idx][i].second=dfs(v[idx][i].first, idx);
			cu=max(cu, v[idx][i].second);
		}
	}
	cu++;
	return cu;
}
pair<int, int>get_val(int idx)
{
	if(a[idx]> 2)
		return make_pair(a[idx], 1);
	vector<int>cu;
	for(int i = 0; i < v[idx].size(); i++)
	{
		if(v[idx][i].second==-1)
			v[idx][i].second=dfs(v[idx][i].first, idx);
		cu.push_back(v[idx][i].second);
	}
	sort(cu.begin(), cu.end());
	reverse(cu.begin(), cu.end());
	if(a[idx]==1)
	{
		if(cu.size()==1)
			return make_pair(1, cu[0]+1);
		return make_pair(1, cu[0]+cu[1]+1);
	}
	if(cu.size()==1)
		return make_pair(2, 1);
	return make_pair(2, 2*min(cu[0],cu[1])+1);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i < n-1; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(make_pair(y, -1));
		v[y].push_back(make_pair(x, -1));
	}
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	pair<long long, long long>ans=make_pair(1000000000LL, 1);
	for(int i = 1; i <= n; i++)
		ans=mi(ans, get_val(i));
	cout << ans.first << ' ' << ans.second << '\n';
}

Compilation message

mag.cpp: In function 'int dfs(int, int)':
mag.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[idx].size(); i++)
                 ~~^~~~~~~~~~~~~~~
mag.cpp: In function 'std::pair<int, int> get_val(int)':
mag.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[idx].size(); i++)
                 ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 483 ms 97272 KB Output isn't correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 580 ms 76496 KB Output isn't correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 554 ms 74248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 535 ms 81884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 29304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 500 ms 73440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 722 ms 74852 KB Output isn't correct
2 Halted 0 ms 0 KB -