oj.uz

Submission #605352

# Submission time Handle Problem Language Result Execution time Memory
605352 2022-07-25T16:07:06 Z jhnah917 Designated Cities (JOI19_designated_cities) C++14
100 / 100
 944 ms 39752 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, Q, Sum, CostTo1, C[202020], R[202020];
vector<pair<int,int>> G[202020];
int S[202020], U[202020];

void TreeDP(int v, int b=-1, ll up=0, ll dw=0){
    for(auto [i,w] : G[v]) if(i == b) CostTo1 += w, up += w;
    C[v] = dw - up;
    for(auto [i,w] : G[v]) if(i != b) TreeDP(i, v, up, dw+w);
}

ll CostToRoot(int root){
    return CostTo1 + C[root];
}

vector<pair<ll,ll>> CostFromRoot(int root){
    vector<pair<ll,ll>> vec;
    function<ll(int,int,int)> dfs = [&](int st, int v, int b) -> ll {
        ll mx = 0;
        for(auto [i,w] : G[v]){
            if(i == b || U[i]) continue;
            ll nxt = dfs(st, i, v) + w;
            if(nxt > mx) swap(nxt, mx);
            if(nxt > 0) vec.emplace_back(nxt, st);
        }
        return mx;
    };
    for(auto [i,w] : G[root]) if(!U[i]) vec.emplace_back(dfs(i, i, -1) + w, i);
    return vec;
}

int GetSize(int v, int b=-1){
    S[v] = 1;
    for(auto [i,w] : G[v]) if(i != b && !U[i]) S[v] += GetSize(i, v);
    return S[v];
}

int GetCent(int v, int tot, int b=-1){
    for(auto [i,w] : G[v]) if(i != b && !U[i] && S[i]*2 > tot) return GetCent(i, tot, v);
    return v;
}

void GetAnswer(int v=1){
    v = GetCent(v, GetSize(v)); U[v] = 1;
    auto vec = CostFromRoot(v);
    sort(vec.begin(), vec.end(), greater<>());

    ll now = CostToRoot(v);
    for(int k=2; k-2<vec.size(); k++){
        if(k-2 < vec.size()) now += vec[k-2].first;
        R[k] = min(R[k], Sum - now);
    }

    int mx2 = -1;
    for(int i=1; i<vec.size(); i++) if(vec[i].second != vec[0].second) { mx2 = i; break; }
    if(mx2 != -1){
        now = CostToRoot(v) + vec[mx2].first;
        vec.erase(vec.begin()+mx2);
        for(int k=2; k-2<vec.size(); k++){
            if(k-2 < vec.size()) now += vec[k-2].first;
            R[k] = min(R[k], Sum - now);
        }
    }

    for(auto [i,w] : G[v]) if(!U[i]) GetAnswer(i);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<N; i++){
        int a, b, c, d; cin >> a >> b >> c >> d; Sum += c + d;
        G[a].emplace_back(b, c); G[b].emplace_back(a, d);
    }
    TreeDP(1);

    memset(R, 0x3f, sizeof R);
    R[1] = Sum - CostTo1 - *max_element(C+1, C+N+1);
    GetAnswer();
    for(int i=2; i<=N; i++) R[i] = min(R[i], R[i-1]);

    cin >> Q;
    for(int i=1; i<=Q; i++){
        int t; cin >> t;
        cout << R[t] << "\n";
    }
}

Compilation message

designated_cities.cpp: In function 'void TreeDP(int, int, ll, ll)':
designated_cities.cpp:10:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   10 |     for(auto [i,w] : G[v]) if(i == b) CostTo1 += w, up += w;
      |              ^
designated_cities.cpp:12:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   12 |     for(auto [i,w] : G[v]) if(i != b) TreeDP(i, v, up, dw+w);
      |              ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:23:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         for(auto [i,w] : G[v]){
      |                  ^
designated_cities.cpp: In function 'std::vector<std::pair<long long int, long long int> > CostFromRoot(int)':
designated_cities.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [i,w] : G[root]) if(!U[i]) vec.emplace_back(dfs(i, i, -1) + w, i);
      |              ^
designated_cities.cpp: In function 'int GetSize(int, int)':
designated_cities.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for(auto [i,w] : G[v]) if(i != b && !U[i]) S[v] += GetSize(i, v);
      |              ^
designated_cities.cpp: In function 'int GetCent(int, int, int)':
designated_cities.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [i,w] : G[v]) if(i != b && !U[i] && S[i]*2 > tot) return GetCent(i, tot, v);
      |              ^
designated_cities.cpp: In function 'void GetAnswer(int)':
designated_cities.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int k=2; k-2<vec.size(); k++){
      |                  ~~~^~~~~~~~~~~
designated_cities.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if(k-2 < vec.size()) now += vec[k-2].first;
      |            ~~~~^~~~~~~~~~~~
designated_cities.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=1; i<vec.size(); i++) if(vec[i].second != vec[0].second) { mx2 = i; break; }
      |                  ~^~~~~~~~~~~
designated_cities.cpp:62:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int k=2; k-2<vec.size(); k++){
      |                      ~~~^~~~~~~~~~~
designated_cities.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(k-2 < vec.size()) now += vec[k-2].first;
      |                ~~~~^~~~~~~~~~~~
designated_cities.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto [i,w] : G[v]) if(!U[i]) GetAnswer(i);
      |              ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 5 ms 6620 KB Output is correct
4 Correct 3 ms 6616 KB Output is correct
5 Correct 5 ms 6620 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 3 ms 6612 KB Output is correct
8 Correct 4 ms 6620 KB Output is correct
9 Correct 4 ms 6620 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 597 ms 19996 KB Output is correct
3 Correct 902 ms 38076 KB Output is correct
4 Correct 542 ms 25124 KB Output is correct
5 Correct 312 ms 25104 KB Output is correct
6 Correct 636 ms 28628 KB Output is correct
7 Correct 221 ms 25668 KB Output is correct
8 Correct 944 ms 37684 KB Output is correct
9 Correct 177 ms 27572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 534 ms 20616 KB Output is correct
3 Correct 793 ms 38136 KB Output is correct
4 Correct 595 ms 25168 KB Output is correct
5 Correct 250 ms 24924 KB Output is correct
6 Correct 679 ms 29232 KB Output is correct
7 Correct 179 ms 27208 KB Output is correct
8 Correct 761 ms 34956 KB Output is correct
9 Correct 166 ms 27104 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 5 ms 6620 KB Output is correct
4 Correct 3 ms 6616 KB Output is correct
5 Correct 5 ms 6620 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 3 ms 6612 KB Output is correct
8 Correct 4 ms 6620 KB Output is correct
9 Correct 4 ms 6620 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 4 ms 6620 KB Output is correct
13 Correct 7 ms 6996 KB Output is correct
14 Correct 8 ms 6892 KB Output is correct
15 Correct 6 ms 6880 KB Output is correct
16 Correct 6 ms 6888 KB Output is correct
17 Correct 6 ms 6884 KB Output is correct
18 Correct 6 ms 6868 KB Output is correct
19 Correct 6 ms 6868 KB Output is correct
20 Correct 5 ms 6832 KB Output is correct
21 Correct 7 ms 6888 KB Output is correct
22 Correct 6 ms 6892 KB Output is correct
23 Correct 5 ms 6920 KB Output is correct
24 Correct 5 ms 6868 KB Output is correct
25 Correct 8 ms 6996 KB Output is correct
26 Correct 5 ms 6868 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 597 ms 19996 KB Output is correct
3 Correct 902 ms 38076 KB Output is correct
4 Correct 542 ms 25124 KB Output is correct
5 Correct 312 ms 25104 KB Output is correct
6 Correct 636 ms 28628 KB Output is correct
7 Correct 221 ms 25668 KB Output is correct
8 Correct 944 ms 37684 KB Output is correct
9 Correct 177 ms 27572 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 534 ms 20616 KB Output is correct
12 Correct 793 ms 38136 KB Output is correct
13 Correct 595 ms 25168 KB Output is correct
14 Correct 250 ms 24924 KB Output is correct
15 Correct 679 ms 29232 KB Output is correct
16 Correct 179 ms 27208 KB Output is correct
17 Correct 761 ms 34956 KB Output is correct
18 Correct 166 ms 27104 KB Output is correct
19 Correct 4 ms 6612 KB Output is correct
20 Correct 545 ms 26432 KB Output is correct
21 Correct 841 ms 38212 KB Output is correct
22 Correct 554 ms 25324 KB Output is correct
23 Correct 558 ms 26444 KB Output is correct
24 Correct 537 ms 25448 KB Output is correct
25 Correct 567 ms 26792 KB Output is correct
26 Correct 515 ms 25372 KB Output is correct
27 Correct 302 ms 25148 KB Output is correct
28 Correct 652 ms 29108 KB Output is correct
29 Correct 491 ms 25904 KB Output is correct
30 Correct 469 ms 26896 KB Output is correct
31 Correct 222 ms 27072 KB Output is correct
32 Correct 795 ms 35304 KB Output is correct
33 Correct 174 ms 27708 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 5 ms 6620 KB Output is correct
4 Correct 3 ms 6616 KB Output is correct
5 Correct 5 ms 6620 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 3 ms 6612 KB Output is correct
8 Correct 4 ms 6620 KB Output is correct
9 Correct 4 ms 6620 KB Output is correct
10 Correct 4 ms 6612 KB Output is correct
11 Correct 3 ms 6612 KB Output is correct
12 Correct 4 ms 6612 KB Output is correct
13 Correct 597 ms 19996 KB Output is correct
14 Correct 902 ms 38076 KB Output is correct
15 Correct 542 ms 25124 KB Output is correct
16 Correct 312 ms 25104 KB Output is correct
17 Correct 636 ms 28628 KB Output is correct
18 Correct 221 ms 25668 KB Output is correct
19 Correct 944 ms 37684 KB Output is correct
20 Correct 177 ms 27572 KB Output is correct
21 Correct 4 ms 6612 KB Output is correct
22 Correct 534 ms 20616 KB Output is correct
23 Correct 793 ms 38136 KB Output is correct
24 Correct 595 ms 25168 KB Output is correct
25 Correct 250 ms 24924 KB Output is correct
26 Correct 679 ms 29232 KB Output is correct
27 Correct 179 ms 27208 KB Output is correct
28 Correct 761 ms 34956 KB Output is correct
29 Correct 166 ms 27104 KB Output is correct
30 Correct 4 ms 6620 KB Output is correct
31 Correct 7 ms 6996 KB Output is correct
32 Correct 8 ms 6892 KB Output is correct
33 Correct 6 ms 6880 KB Output is correct
34 Correct 6 ms 6888 KB Output is correct
35 Correct 6 ms 6884 KB Output is correct
36 Correct 6 ms 6868 KB Output is correct
37 Correct 6 ms 6868 KB Output is correct
38 Correct 5 ms 6832 KB Output is correct
39 Correct 7 ms 6888 KB Output is correct
40 Correct 6 ms 6892 KB Output is correct
41 Correct 5 ms 6920 KB Output is correct
42 Correct 5 ms 6868 KB Output is correct
43 Correct 8 ms 6996 KB Output is correct
44 Correct 5 ms 6868 KB Output is correct
45 Correct 4 ms 6612 KB Output is correct
46 Correct 545 ms 26432 KB Output is correct
47 Correct 841 ms 38212 KB Output is correct
48 Correct 554 ms 25324 KB Output is correct
49 Correct 558 ms 26444 KB Output is correct
50 Correct 537 ms 25448 KB Output is correct
51 Correct 567 ms 26792 KB Output is correct
52 Correct 515 ms 25372 KB Output is correct
53 Correct 302 ms 25148 KB Output is correct
54 Correct 652 ms 29108 KB Output is correct
55 Correct 491 ms 25904 KB Output is correct
56 Correct 469 ms 26896 KB Output is correct
57 Correct 222 ms 27072 KB Output is correct
58 Correct 795 ms 35304 KB Output is correct
59 Correct 174 ms 27708 KB Output is correct
60 Correct 3 ms 6612 KB Output is correct
61 Correct 629 ms 27252 KB Output is correct
62 Correct 875 ms 39752 KB Output is correct
63 Correct 579 ms 25220 KB Output is correct
64 Correct 540 ms 26736 KB Output is correct
65 Correct 543 ms 25400 KB Output is correct
66 Correct 565 ms 27284 KB Output is correct
67 Correct 588 ms 25628 KB Output is correct
68 Correct 301 ms 26320 KB Output is correct
69 Correct 628 ms 30504 KB Output is correct
70 Correct 598 ms 27852 KB Output is correct
71 Correct 499 ms 26404 KB Output is correct
72 Correct 247 ms 27288 KB Output is correct
73 Correct 815 ms 36724 KB Output is correct
74 Correct 190 ms 28516 KB Output is correct