Submission #556338

#	Time	Username	Problem	Language	Result	Execution time	Memory
556338		Olympia	Mag (COCI16_mag)	C++17	24 / 120	922 ms	85576 KiB

mag

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