oj.uz

Submission #240547

# Submission time Handle Problem Language Result Execution time Memory
240547 2020-06-19T22:10:47 Z thecodingwizard Mag (COCI16_mag) C++11
36 / 120
 1763 ms 240892 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n; 
ll A[1000000];
vector<int> adj[1000000];
ll num = 100000000000;
ll denom = 1;

int memoMaxOnesInLine[1000000];
int maxOnesInLine(int u, int p) {
    if (memoMaxOnesInLine[u] != -1) return memoMaxOnesInLine[u];
    if (A[u] != 1) return 0;
    int ans = 1;
    for (int v : adj[u]) {
        if (v != p) ans = max(ans, 1 + maxOnesInLine(v, u));
    }
    return memoMaxOnesInLine[u] = ans;
}

int maxOnesOnly(int u, int p) {
    int best = 0;
    if (A[u] == 1) {
        vector<int> childrenOnesCount;
        for (int v : adj[u]) {
            if (v != p) {
                childrenOnesCount.push_back(maxOnesInLine(v, u));
            }
        }
        sort(childrenOnesCount.begin(), childrenOnesCount.end());
        best = 1;
        if (childrenOnesCount.size()>=1) best = childrenOnesCount[childrenOnesCount.size()-1] + 1;
        if (childrenOnesCount.size()>=2) best += childrenOnesCount[childrenOnesCount.size()-2];
    }
    for (int v : adj[u]) {
        if (v != p) {
            best = max(best, maxOnesOnly(v, u));
        }
    }
    return best;
}

int maxOnesWithTwo(int u, int p, int numOnesFromParent) {
    int best = 0;
    int parentOnes = 0;
    vector<int> childrenOnesCount;
    for (int v : adj[u]) {
        if (v != p) {
            childrenOnesCount.push_back(maxOnesInLine(v, u));
        }
    }
    childrenOnesCount.push_back(numOnesFromParent);
    childrenOnesCount.push_back(0);
    sort(childrenOnesCount.begin(), childrenOnesCount.end());
    if (A[u] == 2) {
        best = childrenOnesCount[childrenOnesCount.size()-1] + childrenOnesCount[childrenOnesCount.size()-2] + 1;
    } else if (A[u] == 1) {
        parentOnes = 1 + numOnesFromParent;
        parentOnes = max(parentOnes, childrenOnesCount.back() + 1);
    }
    for (int v : adj[u]) {
        // warning: parentOnes will be wrong for one node...
        if (v != p) best = max(best, maxOnesWithTwo(v, u, parentOnes));
    }
    return best;
}

int main() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i < n; i++) cin >> A[i];

    num = A[0];
    for (int i = 0; i < n; i++) {
        num = min(num, A[i]);
    }

    for (int i = 0; i < n; i++) {
        memoMaxOnesInLine[i] = -1;
    }

    // case 1: all ones
    int numOnes = maxOnesOnly(0, 0);

    // case 2: one two
    int numOnesWithTwo = maxOnesWithTwo(0, 0, 0);

    if (numOnes==0 || 1.0/numOnes > num) {
        if (numOnesWithTwo==0 || 2.0/numOnesWithTwo > num) {
            cout << num << "/" << 1 << endl;
        } else {
            if (numOnesWithTwo%2==0) {
                cout << "1/" << numOnesWithTwo/2 << endl;
            } else {
                cout << "2/" << numOnesWithTwo << endl;
            }
        }
    } else {
        if (numOnesWithTwo==0 || 2.0/numOnesWithTwo > 1.0/numOnes) {
            cout << "1/" << numOnes << endl;
        } else {
            if (numOnesWithTwo%2==0) {
                cout << "1/" << numOnesWithTwo/2 << endl;
            } else {
                cout << "2/" << numOnesWithTwo << endl;
            }
        }
    }

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23936 KB Output is correct
2 Incorrect 20 ms 23936 KB Output isn't correct

Subtask #2
0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1445 ms 134776 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 82144 KB Output is correct
2 Incorrect 1070 ms 67132 KB Output isn't correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 88204 KB Output is correct
2 Correct 200 ms 29816 KB Output is correct
3 Incorrect 1763 ms 240892 KB Output isn't correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 29560 KB Output is correct
2 Correct 1491 ms 83396 KB Output is correct
3 Correct 975 ms 53624 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1446 ms 81868 KB Output is correct
2 Correct 1577 ms 83324 KB Output is correct

Subtask #10
0 / 12.0

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