oj.uz

Submission #98267

# Submission time Handle Problem Language Result Execution time Memory
98267 2019-02-21T18:14:55 Z dalgerok Mag (COCI16_mag) C++17
12 / 120
 386 ms 37296 KB 
#include<bits/stdc++.h>
using namespace std;



const int N = 1e6 + 5;



int n, p[N], sz[N], a[N];
vector < pair < int, int > > q;

int dsu_get(int v){
    return p[v] == v ? v : p[v] = dsu_get(p[v]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        p[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        q.push_back(make_pair(x, y));
    }
    int ans = -1;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] == 1){
            ans = 1;
        }
    }
    for(auto it : q){
        int x = it.first, y = it.second;
        if(a[x] == 1 && a[y] == 1 && dsu_get(x) != dsu_get(y)){
            sz[dsu_get(y)] += sz[dsu_get(x)];
            ans = max(ans, sz[dsu_get(y)]);
            p[dsu_get(x)] = dsu_get(y);
        }
    }
    if(ans != -1){
        return cout << "1/" << ans, 0;
    }
    ans = 2e9;
    for(int i = 1; i <= n; i++){
        ans = min(ans, a[i]);
    }
    cout << ans << "/1";
}

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 232 ms 30216 KB Output isn't correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 36688 KB Output isn't correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 324 ms 35300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 299 ms 37296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 33804 KB Output is correct
2 Incorrect 386 ms 36744 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 35544 KB Output is correct
2 Incorrect 257 ms 17936 KB Output isn't correct