oj.uz

Submission #133445

# Submission time Handle Problem Language Result Execution time Memory
133445 2019-07-20T17:14:53 Z forelax Mag (COCI16_mag) C++14
120 / 120
 1692 ms 129500 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1337 ms 78924 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 1599 ms 128560 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1655 ms 126356 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1533 ms 66400 KB Output is correct
2 Correct 1152 ms 49052 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1620 ms 67612 KB Output is correct
2 Correct 190 ms 7160 KB Output is correct
3 Correct 1692 ms 129500 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 7132 KB Output is correct
2 Correct 1532 ms 66900 KB Output is correct
3 Correct 970 ms 34276 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1472 ms 61676 KB Output is correct
2 Correct 1637 ms 65784 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1646 ms 67332 KB Output is correct
2 Correct 927 ms 34292 KB Output is correct