Submission #1115275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115275		hqminhuwu	Designated Cities (JOI19_designated_cities)	C++14	16 / 100	350 ms	73032 KiB

designated_cities

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 2e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;

ll lz[N << 2], n, lmao[N], par[N], uwu[N], up[N], dw[N], f[N], g[N], tmp[4], dp[N][3],
 fo[N], leafs, tin[N], tout[N], cnt, vis[N], u, v, w, z, q, ans[N], rf[N];
pll tree[N << 2], ed[N], owo[N];
vector <int> a[N];


void down (int i){
    if (!lz[i]) return;
    forr (j, i << 1, i << 1 | 1){
        tree[j].st += lz[i];
        lz[j] += lz[i];
    }
    lz[i] = 0;
}

void add (int i, int l, int r, int u, int v, ll w, ll z){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        tree[i].st += w;
        tree[i].nd += z;
        lz[i] += w;
        return;
    }
    down(i);
    int mid = l + r >> 1;
    add(i << 1, l, mid, u, v, w, z);
    add(i << 1 | 1, mid + 1, r, u, v, w, z);
    tree[i] = max(tree[i << 1], tree[i << 1 | 1]);    
}

void dfs (int u, int p){
    uwu[u] = u;
    owo[u] = {u, u};

    for (int i : a[u]){
        int v = u ^ ed[i].st ^ ed[i].nd;
        ll w = up[i], z = dw[i];
        if (u == ed[i].st) swap(w, z);

        if (v == p) continue;

        dfs(v, u);
        rf[u] += rf[v] + z;
        f[u] += f[v] + w;
        
        forr (j, 0, 2){
            tmp[j] = dp[u][j] + dp[v][0] + w;
        }
        
        if (maxz(tmp[2], dp[u][0] + dp[v][2] + z)){
            owo[u] = owo[v];        
        }

        if (maxz(tmp[2], dp[u][1] + dp[v][1] + w + z)){
            owo[u] = {uwu[u], uwu[v]};
        }

        if (maxz(tmp[1], dp[u][0] + dp[v][1] + w + z)){
            uwu[u] = uwu[v];
        }

        forr (i, 0, 2){
            dp[u][i] = tmp[i];
        }
    } 
}

void dfs2 (int u, int p){
   // cout << u << " " << f[u] << " " << fo[u] << " " << rf[u] << endl;
    for (int i : a[u]){
        int v = u ^ ed[i].st ^ ed[i].nd;
        ll w = up[i], z = dw[i];
        if (u == ed[i].st) swap(w, z);
        if (v == p) continue; 

        fo[v] = fo[u] + f[u] - f[v] - w + z;

        dfs2(v, u);
    }
}

void dfs3 (int u, int p){
    tin[u] = ++cnt;
    
    if (a[u].size() == 1 && u != p){
        leafs++;
        add(1, 1, n, tin[u], tin[u], g[u], u);
    }

    for (int i : a[u]){
        int v = u ^ ed[i].st ^ ed[i].nd;
        ll w = up[i], z = dw[i];
        if (u == ed[i].st) swap(w, z);
        if (v == p) continue;

        g[v] = g[u] + z;
        par[v] = u;
        lmao[v] = z;

        dfs3(v, u);
    }

    tout[u] = cnt;
}

void bem (int u, ll w = 0){
    add(1, 1, n, tin[u], tout[u], -w, 0);
    if (!vis[u]){
        vis[u] = 1;
        bem(par[u], lmao[u]);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;

    ll sum = 0;

    forf (i, 1, n){
        cin >> u >> v >> w >> z;
        ed[i] = {u, v};
        up[i] = w;
        dw[i] = z;
        a[u].pb(i);
        a[v].pb(i);
        sum += w + z;
    }

    dfs(1, 1);
    dfs2(1, 1);

    dfs3(owo[1].st, owo[1].st);
    vis[owo[1].st] = 1;
    leafs++;
  //  cout << owo[1].st << " " << f[owo[1].st] + fo[owo[1].st] << endl;

    forr (i, 2, leafs){
        ans[i] = ans[i - 1] + tree[1].st;

        if (i == 2){
            ans[i] += f[owo[1].st] + fo[owo[1].st];
        }
        bem(tree[1].nd);
    }

    
    forr (i, 1, n){
        maxz(ans[1], f[i] + fo[i]);
    }

    cin >> q;

    while (q--){
        cin >> u;
        cout << sum - ans[min(u, leafs)] << "\n";
    }

    return 0;
}
/*  



*/

Compilation message (stderr)

designated_cities.cpp: In function 'void add(int, int, int, int, int, ll, ll)':
designated_cities.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~

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