Submission #201748

#	Time	Username	Problem	Language	Result	Execution time	Memory
201748		awlintqaa	Mag (COCI16_mag)	C++14	84 / 120	1644 ms	262148 KiB

mag

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 12 / 12
• Subtask 7: 0 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12