Submission #133445

#	Time	Username	Problem	Language	Result	Execution time	Memory
133445		forelax	Mag (COCI16_mag)	C++14	120 / 120	1692 ms	129500 KiB

mag

#include<bits/stdc++.h>
using namespace std;
long long rezu;
long long rezd;
vector<vector<int> > ng;
vector<int> mg;
vector<int> m1;
vector<int> m2;
inline void attempt(long long a,long long b){
    if(a*rezd<b*rezu){
        rezd=b;
        rezu=a;
    }
}
void solve(int ind,int par){
    if(mg[ind]==2)
        m2[ind]=1;
    else if(mg[ind]==1)
        m1[ind]=1;
    for(int i = 0 ; i < ng[ind].size() ; i ++){
        int ne=ng[ind][i];
        if(ne==par)continue;
        solve(ne,ind);

        if(mg[ind]==2){
            attempt(2,m2[ind]+m1[ne]);
            m2[ind]=max(m2[ind],1+m1[ne]);
        }else if(mg[ind]==1){
            attempt(2,m2[ind]+m1[ne]);
            attempt(2,m1[ind]+m2[ne]);
            attempt(1,m1[ind]+m1[ne]);
            m1[ind]=max(m1[ind],1+m1[ne]);
            m2[ind]=max(m2[ind],1+m2[ne]);
        }
    }
}
int main(){
    int n;
    cin>>n;
    ng.resize(n);
    for(int i = 0,a,b ; i < n-1 ; i ++){
        cin>>a>>b;a--;b--;
        ng[a].push_back(b);
        ng[b].push_back(a);
    }
    mg.resize(n);
    rezd=1;
    rezu=1e9;
    for(int i = 0 ; i < n ; i ++){
        cin>>mg[i];
        if(mg[i]<rezu)
            rezu=mg[i];
    }
    m1.resize(n);
    m2.resize(n);
    solve(0,0);
    if(rezu==2&&rezd%2==0){
        rezd/=rezu;
        rezu=1;
    }
    cout<<rezu<<"/"<<rezd;
}

Compilation message (stderr)

mag.cpp: In function 'void solve(int, int)':
mag.cpp:20:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < ng[ind].size() ; i ++){
                     ~~^~~~~~~~~~~~~~~~

• 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