# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
256486 |
2020-08-02T18:28:49 Z |
amiratou |
Mag (COCI16_mag) |
C++14 |
|
728 ms |
111624 KB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF (int)(1e18)
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
const int MX = 1000006;
vii vec[MX];
int val[MX],two,one;
int solve(int node,int p){
v g;
for(auto &it:vec[node])
if(it.fi!=p && (val[it.fi]==1)){
if(it.se==-1)it.se=solve(it.fi,node);
g.pb(it.se);
}
sort(all(g),greater<int>());
if((node==p) && (val[node]==2) && (sz(g)>=2))two=max(two,g[0]+g[1]+1);
if((node==p) && (val[node]==1) && (sz(g)>=1))one=max(one,g[0]+1);
return ((sz(g)?g[0]:0)+(val[node]==1))*(val[node]==1);
}
int32_t main(){
boost;
//freopen(".in","r",stdin);
ii ans={INF,1};
int n,a,b;
cin>>n;
for (int i = 0; i < n-1; ++i)
{
cin>>a>>b;
a--,b--;
vec[a].pb({b,-1});
vec[b].pb({a,-1});
}
for (int i = 0; i < n; ++i){
cin>>val[i];
if(val[i]<ans.fi)ans.fi=val[i];
}
for (int i = 0; i < n; ++i)
solve(i,i);
if(one || two){
if(!two)ans={1,one};
else{
if((2*one)>=two)ans={1,one};
else ans={2,two};
}
}
int g=__gcd(ans.fi,ans.se);
cout<<ans.fi/g<<"/"<<ans.se/g<<"\n";
return 0;
}
//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23808 KB |
Output is correct |
2 |
Correct |
19 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23808 KB |
Output is correct |
2 |
Correct |
16 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
565 ms |
111624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
508 ms |
78072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
582 ms |
79416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
593 ms |
78388 KB |
Output is correct |
2 |
Correct |
439 ms |
63992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
460 ms |
84944 KB |
Output is correct |
2 |
Correct |
142 ms |
29848 KB |
Output is correct |
3 |
Correct |
629 ms |
78708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
29800 KB |
Output is correct |
2 |
Correct |
635 ms |
79192 KB |
Output is correct |
3 |
Correct |
728 ms |
53500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
558 ms |
75088 KB |
Output is correct |
2 |
Correct |
638 ms |
77812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
603 ms |
78968 KB |
Output is correct |
2 |
Correct |
649 ms |
53624 KB |
Output is correct |