oj.uz

Submission #702683

# Submission time Handle Problem Language Result Execution time Memory
702683 2023-02-24T19:41:17 Z jhnah917 Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 126036 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[v]*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);
    }

    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=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 'int GetSize(int, int)':
designated_cities.cpp:11:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |     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:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [i,w] : G[v]) if(i != b && !U[i] && S[v]*2 > n) return GetCent(i, n, v);
      |              ^
designated_cities.cpp: In function 'void TreeDP(int, int, ll, ll)':
designated_cities.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for(auto [i,w] : G[v]) if(i == b) C1 += w, up += w;
      |              ^
designated_cities.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [i,w] : G[v]) if(i != b) TreeDP(i, v, up, dw+w);
      |              ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:34:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         for(auto [i,w] : G[v]){
      |                  ^
designated_cities.cpp: In function 'std::vector<std::pair<long long int, long long int> > PathsFromRoot(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[root]) if(!U[i]) paths.emplace_back(dfs(i, i, root) + w, i);
      |              ^
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);
      |                      ~^~~~~~~~~~~~~
designated_cities.cpp:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for(auto [i,w] : G[root]) if(!U[i]) Go(i);
      |              ^

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Execution timed out 2051 ms 119380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Execution timed out 2070 ms 126036 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 9 ms 5844 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 10 ms 6228 KB Output is correct
16 Correct 9 ms 5788 KB Output is correct
17 Correct 8 ms 5716 KB Output is correct
18 Correct 9 ms 5940 KB Output is correct
19 Correct 9 ms 5972 KB Output is correct
20 Correct 32 ms 11644 KB Output is correct
21 Correct 15 ms 7448 KB Output is correct
22 Correct 10 ms 6100 KB Output is correct
23 Correct 9 ms 6100 KB Output is correct
24 Correct 147 ms 38368 KB Output is correct
25 Correct 18 ms 9056 KB Output is correct
26 Correct 155 ms 40524 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Execution timed out 2051 ms 119380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 2 ms 5076 KB Output is correct
13 Execution timed out 2051 ms 119380 KB Time limit exceeded
14 Halted 0 ms 0 KB -