oj.uz

Submission #472658

# Submission time Handle Problem Language Result Execution time Memory
472658 2021-09-14T04:34:32 Z ITO Designated Cities (JOI19_designated_cities) C++11
0 / 100
 556 ms 33720 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define no cout << "ickgf\n"
using namespace std;
typedef long long ll;
int n, mi1, mi2;
ll an[200001], ma = 0;
vector<pair<int, pair<int, int>>> e[200001];
priority_queue<pair<ll, int>> pq[200001];
pair<int, int> eat(int x, int p){
    pair<ll, ll> re = {0, 0}, tm;
    for (pair<int, pair<int, int>> pi : e[x]) {
        if (pi.first != p) {
            tm = eat(pi.first, x);
            re.first += tm.first + pi.second.second;
            re.second = max(re.second, tm.second + pi.second.first - pi.second.second);
        }
    }
    return re;
}
pair<int, int> nom(int x, int p, ll ba) {
    pair<ll, ll> m1 = {0, 0}, m2 = {0, 0}, tm;
    for (pair<int, pair<int, int>> pi : e[x]) {
        if (pi.first != p) {
            tm = nom(pi.first, x, ba + pi.second.first - pi.second.second);
            tm.first += (ll) pi.second.first;
            if (tm.first > m1.first) {
                m2 = m1, m1 = tm;
            } else if (tm.first > m2.first) {
                m2 = tm;
            }
        }
    }
    if (m2.first > 0ll) {
        ba += m1.first + m2.first;
        if (ba > ma) {
            ma = ba, mi1 = m1.second, mi2 = m2.second;
        }
    } else if (m1.first == 0ll) {
        m1.second = x;
    }
    return m1;
}
ll yum(int x, int p){
    if (e[x].size() == 1 && p != 0) {
        return 0;
    }
    for (pair<int, pair<int, int>> pi : e[x]) {
        if (pi.first != p) {
            pq[x].push({yum(pi.first, x) + pi.second.first, pi.first});
        }
    }
    return pq[x].top().first;
}
void mhm(int x) {
    if (!pq[x].empty()) {
        pair<ll, int> ppp = pq[x].top();
        pq[x].pop();
        mhm(ppp.second);
    }
    while (!pq[x].empty()) {
        pq[mi1].push(pq[x].top());
        pq[x].pop();
    }
}
int main(){
    int a, b, c, d, ej, q;
    ll tot = 0;
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> c >> d;
        e[a].push_back({b, {c, d}});
        e[b].push_back({a, {d, c}});
        tot += (ll) c + d;
    }
    if (n == 2) {
        an[1] = min(c, d);
    } else {
        int sta = 1;
        if (e[1].size() == 1) {
            sta = e[1][0].first;
        }
        pair<ll, ll> re = eat(sta, 0), re2 = nom(sta, 0, re.first);
        an[1] = tot - re.first - re.second;
        yum(mi1, 0);
        tot -= ma;
        an[2] = tot;
        pair<ll, int> ppp;
        ppp = pq[mi1].top();
        pq[mi1].pop();
        mhm(ppp.second);
        for (int i = 3; tot > 0 && i <= n; i++) {
            ppp = pq[mi1].top();
            pq[mi1].pop();
            mhm(ppp.second);
            tot -= ppp.first;
            an[i] = tot;
        }
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> ej;
        cout << an[ej] << '\n';
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:83:40: warning: variable 're2' set but not used [-Wunused-but-set-variable]
   83 |         pair<ll, ll> re = eat(sta, 0), re2 = nom(sta, 0, re.first);
      |                                        ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Incorrect 7 ms 11212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Incorrect 539 ms 33720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11212 KB Output is correct
2 Incorrect 556 ms 33652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Incorrect 7 ms 11212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Incorrect 539 ms 33720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Incorrect 7 ms 11212 KB Output isn't correct
3 Halted 0 ms 0 KB -