Submission #702678

#	Time	Username	Problem	Language	Result	Execution time	Memory
702678		jhnah917	Designated Cities (JOI19_designated_cities)	C++14	0 / 100	6 ms	10068 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

ll DFS1(int v, int b=-1){
    ll res = 0;
    for(auto [i,w] : G[v]) res += b != i ? DFS1(i, v) : w;
    return res;
}

ll DFS2(vector<ll> &vec, int v, int b=-1){
    ll mx = 0;
    for(auto [i,w] : G[v]){
        if(i == b) continue;
        ll nxt = DFS2(vec, i, v) + w;
        if(nxt > mx) swap(mx, nxt);
        if(nxt != 0) vec.push_back(nxt);
    }
    return mx;
}

void Go(int root){
    ll to_root = DFS1(root);
    vector<pair<ll,ll>> paths;
    for(auto [i,w] : G[root]){
        vector<ll> now; DFS2(now, i);
        for(auto j : now) paths.emplace_back(j+w, i);
    }
    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 = paths[0].first + paths[idx].first;
        R[2] = max(R[2], cost3);
        paths.erase(paths.begin() + idx);
        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);
    }
    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 (stderr)

designated_cities.cpp: In function 'll DFS1(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]) res += b != i ? DFS1(i, v) : w;
      |              ^
designated_cities.cpp: In function 'll DFS2(std::vector<long long int>&, int, int)':
designated_cities.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [i,w] : G[v]){
      |              ^
designated_cities.cpp: In function 'void Go(int)':
designated_cities.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto [i,w] : G[root]){
      |              ^
designated_cities.cpp:42: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]
   42 |     for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost2 += paths[i].first);
      |                  ~^~~~~~~~~~~~~
designated_cities.cpp:46: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]
   46 |     if(idx != paths.size()){
      |        ~~~~^~~~~~~~~~~~~~~
designated_cities.cpp:50: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]
   50 |         for(int i=1; i<paths.size(); i++) R[i+2] = max(R[i+2], cost3 += paths[i].first);
      |                      ~^~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44