Submission #611841

#	Time	Username	Problem	Language	Result	Execution time	Memory
611841		alireza_kaviani	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	620 ms	105456 KiB

designated_cities

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())
#define lc          id << 1
#define rc          lc | 1

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , q , cost , root , timer , ans[MAXN] , H[MAXN] , st[MAXN] , fn[MAXN] , par[MAXN] , W[MAXN] , ind[MAXN] , mark[MAXN] , lz[MAXN << 2];
pll seg[MAXN << 2];
vector<pii> adj[MAXN] , g[MAXN];

void PreDFS(int v , int p = -1){
    ans[1] = min(ans[1] , H[v]);
    for(pii i : g[v]){
        int u = i.X , w = i.Y;
        if(u == p)  continue;
        H[u] = H[v] + w;
        PreDFS(u , v);
    }
}

void DistDFS(int v , int p = -1){
    ind[timer] = v;
    st[v] = timer++;
    for(pii i : adj[v]){
        int u = i.X , w = i.Y;
        if(u == p)  continue;
        cost += w;
        par[u] = v; W[u] = w;
        H[u] = H[v] + w;
        DistDFS(u , v);
    }
    fn[v] = timer;
}

void build(int id = 1 , int l = 0 , int r = n){
    if(r - l == 1){
        seg[id] = {H[ind[l]] , ind[l]};
        return;
    }
    int mid = l + r >> 1;
    build(lc , l , mid);
    build(rc , mid , r);
    seg[id] = max(seg[lc] , seg[rc]);
}

void shift(int id){
    seg[lc].X += lz[id]; lz[lc] += lz[id];
    seg[rc].X += lz[id]; lz[rc] += lz[id];
    lz[id] = 0;
}

void update(int ql , int qr , int x , int id = 1 , int l = 0 , int r = n){
    if(qr <= l || r <= ql)  return;
    if(ql <= l && r <= qr){
        seg[id].X += x;
        lz[id] += x;
        return;
    }
    shift(id);
    int mid = l + r >> 1;
    update(ql , qr , x , lc , l , mid);
    update(ql , qr , x , rc , mid , r);
    seg[id] = max(seg[lc] , seg[rc]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n;
    for(int i = 1 ; i < n ; i++){
        int v , u , w1 , w2;
        cin >> v >> u >> w1 >> w2;
        adj[v].push_back({u , w1});
        adj[u].push_back({v , w2});
        g[v].push_back({u , w2 - w1});
        g[u].push_back({v , w1 - w2});
    }

    PreDFS(1);
    DistDFS(1);
    ans[1] += cost;
    root = max_element(H , H + MAXN) - H;
    H[root] = cost = timer = 0;
    DistDFS(root);
    mark[root] = 1;

    build();
    for(int i = 2 ; i <= n ; i++){
        int v = seg[1].Y;
        while(!mark[v]){
            cost -= W[v];
            update(st[v] , fn[v] , -W[v]);
            mark[v] = 1;
            v = par[v];
        }
        ans[i] = cost;
    }
    
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }

    return 0;
}
/*

*/

Compilation message (stderr)

designated_cities.cpp: In function 'void build(int, int, int)':
designated_cities.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
designated_cities.cpp: In function 'void update(int, int, int, int, int, int)':
designated_cities.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = l + r >> 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