oj.uz

Submission #717696

# Submission time Handle Problem Language Result Execution time Memory
717696 2023-04-02T10:54:31 Z walterw Designated Cities (JOI19_designated_cities) C++17
16 / 100
 382 ms 44672 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

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 n, int b=-1){
    for(auto [i,w] : G[v]) if(i != b && !U[i] && S[i]*2 > n) return GetCent(i, n, v);
    return v;
}

void TreeDP(int v, int b=-1, ll up=0, ll dw=0){
    for(auto [i,w] : G[v]) if(i == b) C1 += 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 C1 + C[root];
}

vector<pair<ll,ll>> PathsFromRoot(int root){
    vector<pair<ll,ll>> paths;
    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(mx, nxt);
            if(mx != 0) paths.emplace_back(nxt, st);
        }
        return mx;
    };
    for(auto [i,w] : G[root]) if(!U[i]) paths.emplace_back(dfs(i, i, root) + w, i);
    return paths;
}

void Go(int root){
    root = GetCent(root, GetSize(root)); U[root] = 1;

    ll to_root = CostToRoot(root);
    vector<pair<ll,ll>> paths = PathsFromRoot(root);
    sort(paths.begin(), paths.end(), greater<>());

    // case 1. only root
    R[1] = max(R[1], to_root);
    if(paths.empty()) return;

    // case 2. root and some leaves
    ll cost2 = to_root + paths[0].first;
    R[2] = max(R[2], cost2);
    for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost2 += paths[i].first);

    // case 3. only leaves
    int idx = find_if(paths.begin(), paths.end(), [&](auto v){ return paths[0].second != v.second; }) - paths.begin();
    if(idx != paths.size()){
        ll cost3 = to_root + paths[0].first + paths[idx].first;
        paths.erase(paths.begin() + idx);
        R[2] = max(R[2], cost3);
        for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost3 += paths[i].first);
    }

    return;
    for(auto [i,w] : G[root]) if(!U[i]) Go(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);
    Go(1);
    for (int i = 1; i <= N; i++) R[1] = max(R[1], CostToRoot(i));
    for(int i=2; i<=N; i++) R[i] = max(R[i], R[i-1]);
    cin >> Q;
    for(int i=1,t; i<=Q; i++) cin >> t, cout << Sum - R[t] << "\n";
}

Compilation message

designated_cities.cpp: In function 'void Go(int)':
designated_cities.cpp:60: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]
   60 |     for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost2 += paths[i].first);
      |                  ~^~~~~~~~~~~~~
designated_cities.cpp:64:12: 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]
   64 |     if(idx != paths.size()){
      |        ~~~~^~~~~~~~~~~~~~~
designated_cities.cpp:68:23: 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]
   68 |         for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost3 += paths[i].first);
      |                      ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 5084 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Incorrect 3 ms 5076 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 290 ms 28752 KB Output is correct
3 Correct 345 ms 44628 KB Output is correct
4 Correct 300 ms 27372 KB Output is correct
5 Correct 300 ms 28828 KB Output is correct
6 Correct 342 ms 31004 KB Output is correct
7 Correct 256 ms 28256 KB Output is correct
8 Correct 382 ms 43960 KB Output is correct
9 Correct 199 ms 29468 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 303 ms 22856 KB Output is correct
3 Correct 360 ms 38656 KB Output is correct
4 Correct 303 ms 22852 KB Output is correct
5 Correct 310 ms 22868 KB Output is correct
6 Correct 299 ms 25596 KB Output is correct
7 Correct 215 ms 23348 KB Output is correct
8 Correct 333 ms 33140 KB Output is correct
9 Correct 161 ms 23356 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 5084 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Incorrect 3 ms 5076 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 290 ms 28752 KB Output is correct
3 Correct 345 ms 44628 KB Output is correct
4 Correct 300 ms 27372 KB Output is correct
5 Correct 300 ms 28828 KB Output is correct
6 Correct 342 ms 31004 KB Output is correct
7 Correct 256 ms 28256 KB Output is correct
8 Correct 382 ms 43960 KB Output is correct
9 Correct 199 ms 29468 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 303 ms 22856 KB Output is correct
12 Correct 360 ms 38656 KB Output is correct
13 Correct 303 ms 22852 KB Output is correct
14 Correct 310 ms 22868 KB Output is correct
15 Correct 299 ms 25596 KB Output is correct
16 Correct 215 ms 23348 KB Output is correct
17 Correct 333 ms 33140 KB Output is correct
18 Correct 161 ms 23356 KB Output is correct
19 Correct 4 ms 5076 KB Output is correct
20 Correct 327 ms 28860 KB Output is correct
21 Correct 359 ms 44672 KB Output is correct
22 Correct 288 ms 27380 KB Output is correct
23 Correct 302 ms 29168 KB Output is correct
24 Incorrect 320 ms 27968 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 5084 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Incorrect 3 ms 5076 KB Output isn't correct
9 Halted 0 ms 0 KB -