oj.uz

Submission #702682

# Submission time Handle Problem Language Result Execution time Memory
702682 2023-02-24T19:38:25 Z jhnah917 Designated Cities (JOI19_designated_cities) C++14
23 / 100
 261 ms 10068 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];

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) 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]) paths.emplace_back(dfs(i, i, root) + w, i);
    return paths;
}

void Go(int root){
    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);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N; assert(N <= 2000);
    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);
    for(int i=1; i<=N; i++) Go(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 TreeDP(int, int, ll, ll)':
designated_cities.cpp:9:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
    9 |     for(auto [i,w] : G[v]) if(i == b) C1 += w, up += w;
      |              ^
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) TreeDP(i, v, up, dw+w);
      |              ^
designated_cities.cpp: In lambda function:
designated_cities.cpp:22:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         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:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [i,w] : G[root]) paths.emplace_back(dfs(i, i, root) + w, i);
      |              ^
designated_cities.cpp: In function 'void Go(int)':
designated_cities.cpp:46: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]
   46 |     for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost2 += paths[i].first);
      |                  ~^~~~~~~~~~~~~
designated_cities.cpp:50: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]
   50 |     if(idx != paths.size()){
      |        ~~~~^~~~~~~~~~~~~~~
designated_cities.cpp:54: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]
   54 |         for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost3 += paths[i].first);
      |                      ~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5084 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5080 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 Runtime error 7 ms 10060 KB Execution killed with signal 6
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 Runtime error 7 ms 10068 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5084 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5080 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 261 ms 5336 KB Output is correct
14 Correct 179 ms 5608 KB Output is correct
15 Correct 251 ms 5320 KB Output is correct
16 Correct 234 ms 5332 KB Output is correct
17 Correct 236 ms 5320 KB Output is correct
18 Correct 259 ms 5336 KB Output is correct
19 Correct 233 ms 5324 KB Output is correct
20 Correct 247 ms 5324 KB Output is correct
21 Correct 238 ms 5580 KB Output is correct
22 Correct 237 ms 5348 KB Output is correct
23 Correct 244 ms 5332 KB Output is correct
24 Correct 247 ms 5320 KB Output is correct
25 Correct 228 ms 5604 KB Output is correct
26 Correct 248 ms 5332 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 Runtime error 7 ms 10060 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5084 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5080 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 Runtime error 7 ms 10060 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -