Submission #1047846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047846		ooscode	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	356 ms	130896 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()

const int N = 3e5 + 10;
const int INF = 1e18 + 10;
const int mod = 1e9 + 7;

int n;
vector<pair<int , pair<int , int>>> g[N];
int ans[N];
int dp[N];
int dw[N];
int up[N];
vector<int> pre[N];
vector<int> suf[N];
int pos[N];

void efs(int v , int pr) {
    for(auto [u , w] : g[v]) if(u != pr) {
        efs(u , v);
        dp[v] += dp[u] + w.S;
    }
}

int root;

void rer(int v , int pr) {
    ans[1] = max(ans[1] , dp[v]);

    // cout << v << " : " << dp[v] << " " << max(dw[v] , up[v]) << " tet\n";

    if(ans[2] < dp[v] + max(dw[v] , up[v])) {ans[2] = dp[v] + max(dw[v] , up[v]) , root = v;}

    for(auto [u , w] : g[v]) if(u != pr) {
        dp[v] -= dp[u] + w.S;
        dp[u] += dp[v] + w.F;
        rer(u , v);
        dp[u] -= dp[v] + w.F;
        dp[v] += dp[u] + w.S;
    }
}

void kfs(int v , int pr) {
    for(auto [u , w] : g[v]) if(u != pr) {
        kfs(u , v);
        dw[v] = max(dw[v] , dw[u] + w.F);
        pos[u] = pre[v].size();
        pre[v].pb(dw[v]);
    }

    for(int i = g[v].size()-1 ; ~i ; i--) {
        int u = g[v][i].F;
        auto w = g[v][i].S;
        if(u == pr) continue;
        int x = dw[u] + w.F;
        if(suf[v].size()) suf[v].pb(max(suf[v].back() , x));
        else suf[v].pb(x);
    }
    reverse(all(suf[v]));
}

void lfs(int v , int pr) {
    for(auto [u , w] : g[v]) if(u != pr) {
        up[u] = up[v];
        int p = pos[u];
        if(p != 0) up[u] = max(up[u] , pre[v][p-1]);
        if(p != suf[v].size() - 1) up[u] = max(up[u] , suf[v][p+1]);
        up[u] += w.S;
        lfs(u , v);
    }
}

multiset<int> s[N];

void dfs(int v , int pr) {
    s[v].insert(0);
    for(auto [u , w] : g[v]) if(u != pr) {
        dfs(u , v);
        
        int x = *(--s[u].end());
        s[u].erase(--s[u].end());
        s[u].insert(x + w.F);

        if(s[u].size() > s[v].size()) s[v].swap(s[u]);
        for(auto p : s[u]) s[v].insert(p);
    }

    // cout << v << " :\n";
    // for(auto x : s[v]) cout << x << " ";
    // cout << "\n";
}

void solve() {
    cin >> n;

    if(n == 2) {
        int x , y;
        cin >> x >> y >> x >> y;
        int q;
        cin >> q;
        while(q--) {
            int z;
            cin >> z;
            if(z == 1) cout << min(x , y) << "\n";
            else cout << "0\n";
        } 
        return;
    }

    int f = 0;
    for(int i = 1 ; i < n ; i++) {
        int v , u , a , b; 
        cin >> v >> u >> a >> b; f += a + b;
        g[v].pb({u , {a , b}});
        g[u].pb({v , {b , a}});
    }

    // cout << "\n";

    kfs(1 , -1);
    lfs(1 , -1);

    // for(int i = 1 ; i <= n ; i++)
    // cout << i << " " << dw[i] << " " << up[i] << "\n";

    efs(1 , -1);
    ans[1] = dp[1];
    rer(1 , -1);
    ans[1] = ans[1];
    ans[2] = ans[2];

    dfs(root , -1);

    // cout << root << "\n";

    int q;
    cin >> q;

    int p = 3;
    s[root].erase(--s[root].end());
    while(s[root].size()) 
        ans[p] = ans[p-1] + *(--s[root].end()) , p++ , s[root].erase(--s[root].end());

    while(q--) {
        int x;
        cin >> x;
        cout << f - ans[x] << "\n";
    }
} 

/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2

5
1 2 1 2
2 3 2 3
3 4 3 4
4 5 4 5
5
1 2 3 4 5
*/

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

Compilation message (stderr)

designated_cities.cpp: In function 'void lfs(long long int, long long int)':
designated_cities.cpp:74:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if(p != suf[v].size() - 1) up[u] = max(up[u] , suf[v][p+1]);
      |            ~~^~~~~~~~~~~~~~~~~~~~

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