oj.uz

Submission #537256

# Submission time Handle Problem Language Result Execution time Memory
537256 2022-03-14T20:39:34 Z ali22413836 Mag (COCI16_mag) C++14
120 / 120
 398 ms 158604 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23864 KB Output is correct
2 Correct 18 ms 23892 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 106564 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 394 ms 155480 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 155360 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 93544 KB Output is correct
2 Correct 243 ms 75064 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 97812 KB Output is correct
2 Correct 89 ms 31412 KB Output is correct
3 Correct 395 ms 158604 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 31252 KB Output is correct
2 Correct 351 ms 93860 KB Output is correct
3 Correct 286 ms 61764 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 90512 KB Output is correct
2 Correct 335 ms 94612 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 94540 KB Output is correct
2 Correct 301 ms 61872 KB Output is correct