| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 256453 |
2020-08-02T17:38:07 Z |
ElyesChaabouni |
Mag (COCI16_mag) |
C++14 |
|
612 ms |
83836 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++)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
19 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
16 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
474 ms |
83836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
581 ms |
74360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
579 ms |
59640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
542 ms |
59384 KB |
Output is correct |
| 2 |
Correct |
396 ms |
60792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
522 ms |
64732 KB |
Output is correct |
| 2 |
Correct |
120 ms |
29672 KB |
Output is correct |
| 3 |
Correct |
574 ms |
76560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
28408 KB |
Output is correct |
| 2 |
Correct |
549 ms |
74932 KB |
Output is correct |
| 3 |
Correct |
577 ms |
52184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
604 ms |
58716 KB |
Output is correct |
| 2 |
Correct |
612 ms |
75640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
575 ms |
60408 KB |
Output is correct |
| 2 |
Correct |
508 ms |
52104 KB |
Output is correct |
