oj.uz

Submission #201748

# Submission time Handle Problem Language Result Execution time Memory
201748 2020-02-11T22:37:05 Z awlintqaa Mag (COCI16_mag) C++14
84 / 120
 1644 ms 262148 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1e9+7;
const ll inf=1e18;
const ld pai=acos(-1);
int n;
vi v[1000009];
int a[1000009];
int dpdn[1000009];
void dfs1(ll node,ll p){
        for(auto u:v[node]){
                if(u==p)C;
                dfs1(u,node);
                if(a[u]!=1)C;
                dpdn[node]=max(dpdn[node],dpdn[u]+1);
        }
}
int dpup[1000009];
void dfs2(ll node,ll p){
        vi pre,suf;
        pre.pb(0),suf.pb(0);
        for(auto u:v[node]){
                if(u==p)C;
                int val=0;
                if(a[u]==1)val=dpdn[u]+1;
                pre.pb(max(pre[pre.size()-1],val));
        }
        for(int i=v[node].size()-1;i>=0;i--){
                int u=v[node][i];
                if(u==p)C;
                int val=0;
                if(a[u]==1)val=dpdn[u]+1;
                suf.pb(max(suf[suf.size()-1],val));
        }reverse(suf.begin(),suf.end());
        int it=0;
        for(auto u:v[node]){
                if(u==p)C;
                it++;
                int mx=0;
                int bef=pre[it-1];
                int aft=suf[it];
                if(a[node]==1)mx=max(dpup[node],max(bef,aft))+1;
                dpup[u]=mx;
                dfs2(u,node);
        }
}
pll ans={1e9,1};
bool yes(pll a,pll b){
        return (ll)a.fi*b.se<(ll)b.fi*a.se;
}
void calc(int node,int p){
        pll ret={a[node],1};
        if(yes(ret,ans))ans=ret;
        ll mx=dpup[node];
        for(auto u:v[node]){
                if(u==p)C;
                ll val=0;
                if(a[u]==1)val=dpdn[u]+1;
                ret={a[node],1+val+mx};
                if(yes(ret,ans))ans=ret;
                mx=max(mx,val);
                calc(u,node);
        }
}
int main(){
        cin>>n;
        for(int i=0;i<n-1;i++){
                int a,b;
                cin>>a>>b;
                a--,b--;
                v[a].pb(b);
                v[b].pb(a);
        }
        for(int i=0;i<n;i++)cin>>a[i];
        dfs1(0,0);
        dfs2(0,0);
        calc(0,0);
        ll G=__gcd(ans.fi,ans.se);
        cout<<(ll)ans.fi/G<<"/"<<(ll)ans.se/G<<endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23928 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 20 ms 23928 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 146036 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Runtime error 1625 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1623 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 66740 KB Output is correct
2 Correct 1053 ms 55928 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1480 ms 70484 KB Output is correct
2 Correct 207 ms 28280 KB Output is correct
3 Runtime error 1644 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 28408 KB Output is correct
2 Correct 1401 ms 68680 KB Output is correct
3 Correct 924 ms 45944 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 67440 KB Output is correct
2 Correct 1492 ms 66424 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 68116 KB Output is correct
2 Correct 931 ms 45936 KB Output is correct