Submission #537256

#	Time	Username	Problem	Language	Result	Execution time	Memory
537256		ali22413836	Mag (COCI16_mag)	C++14	120 / 120	398 ms	158604 KiB

mag

#include <bits/stdc++.h>
#define  endl "\n"
using namespace std ;
typedef long long ll;
typedef long double ld ;
const int N=2e7;
const ll inf=1e18 ;
const ll mod = 1e9 + 7 ;
ll mypower(ll x, ll y){
    if(y == 0) return 1 ;
    if(y == 1) return x ;
    ll ret = mypower(x , y / 2);
    ret = (ret * ret) % mod;
    if(y % 2) ret = ( ret * x ) % mod ;
    return ret ;
}
ll dp1[1000006] , dp2[1000006] , n , a[1000006] ;
vector < ll > v[1000006] ;
void update(ll node , ll x){
    dp2[node] = max(dp2[node] , x) ;
    if(dp1[node] < dp2[node]){
        swap(dp1[node] , dp2[node]) ;
    }
    return ;
}
void dfs(ll node, ll par){
    for (auto p : v[node]){
        if (p == par) continue;
        dfs(p , node);
        if (a[p] == 1) update(node, dp1[p] + 1);
    }
}
void dfs1(ll node , ll par){
    for (auto p : v[node]){
        if (p == par) continue;
        if (a[node] == 1){
            if ((dp1[p] + 1) == dp1[node]) update(p , dp2[node] + 1) ;
            else update(p, dp1[node] + 1) ;
        }
        dfs1(p , node) ;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n ;
    for(int i = 1 ; i < n ; i ++){
        ll x , y ;
        cin >> x >> y ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i] ;
    }
    dfs(1 , 1) ;
    dfs1(1  ,1) ;
    pair < ll , ll > ans = {1e18 , 1} ;
    for(int i = 1 ; i <= n;  i++){
        if(a[i] * ans.second < ans.first *(dp1[i] + dp2[i] + 1))
            ans = {a[i] , dp1[i] + dp2[i] + 1} ;
    }
    ll q = __gcd(ans.first , ans.second) ;
    ans.first /= q ;
    ans.second /= q ;
    cout << ans.first << "/" << ans.second << endl ;
    return 0 ;
}
		

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12