oj.uz

Submission #556338

# Submission time Handle Problem Language Result Execution time Memory
556338 2022-05-03T02:08:47 Z Olympia Mag (COCI16_mag) C++17
24 / 120
 922 ms 85576 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> depth;
vector<int> val;
void dfs (vector<int>& tot, vector<vector<int> >& adj, vector<bool> &hasVisited, int curNode, int prevNode) {
    if (val[curNode] != 1) {
        return;
    }
    if (curNode == prevNode) {
        depth[curNode] = 0;
    } else {
        depth[curNode] = depth[prevNode] + 1;
    }
    hasVisited[curNode] = true;
    for (int i: adj[curNode]) {
        if (i != prevNode) {
            dfs (tot, adj, hasVisited, i, curNode);
        }
    }
    tot.push_back(curNode);
}
int main() {
    vector<vector<int> > adj;
    int n;
    cin >> n;
    adj.resize(n), depth.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    val.resize(n);
    int myMin = INT_MAX;
    for (int i = 0; i < n; i++) {
        cin >> val[i];
        myMin = min(myMin, val[i]);
    }
    if (myMin >= 2) {
        cout << myMin << "/" << 1;
        return 0;
    }
    vector<bool> hasVisited;
    hasVisited.assign(n, false);
    int myMax = 0;
    for (int i = 0; i < n; i++) {
        if (hasVisited[i] || val[i] != 1) {
            continue;
        }
        vector<int> tot;
        dfs (tot, adj, hasVisited, i, i);
        pair<int,int> p = make_pair(-1, -1);
        for (int j: tot) {
            p = max(p, make_pair(depth[j], j));
        }
        int u = p.second;
        p = make_pair(-1, -1);
        tot.clear();
        dfs (tot, adj, hasVisited, u, u);
        for (int j: tot) {
            p = max(p, make_pair(depth[j], j));
        }
        int v = p.second;
        myMax = max(myMax, abs(depth[u] - depth[v]) + 1);
    }
    cout << 1 << "/" << myMax;

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7028 KB Output is correct
2 Incorrect 879 ms 78512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 58764 KB Output is correct
2 Incorrect 877 ms 78904 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 63408 KB Output is correct
2 Correct 515 ms 40728 KB Output is correct