Submission #1034323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034323		Shayan86	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	254 ms	58448 KiB

designated_cities

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

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define SZ(x)       (int)x.size()
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 50;
const ll inf = 1e18;

ll n, val, res[N], h[N], timer, st[N], ft[N], tim[N];
pll par[N];

bool mark[N];
vector<pair<int, pii>> adj[N];

void dfs1(int v, int p = 0){
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        dfs1(u, v); val += w.F;
    }
}

void dfs2(int v, int p = 0){
    res[1] = min(res[1], val);
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        val += w.S - w.F;
        dfs2(u, v);
        val -= w.S - w.F;
    }
}

void dfs3(int v, int p = 0){
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        h[u] = h[v] + w.F;
        dfs3(u, v);
    }
}

void dfs(int v, int p = 0){
    tim[timer] = v;
    st[v] = timer++;
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        h[u] = h[v] + w.F;
        res[1] += w.F;
        par[u] = {v, w.F};
        dfs(u, v);
    }
    ft[v] = timer;
}

pll seg[N*4]; ll lz[N*4];

void build(int l, int r, int id = 1){
    if(l+1 == r){
        seg[id] = {h[tim[l]], tim[l]};
        return;
    }
    build(l, mid, lid);
    build(mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

void quex(int id, ll x){
    seg[id].F += x; lz[id] += x;
}

void relax(int id){
    quex(lid, lz[id]);
    quex(rid, lz[id]);
    lz[id] = 0;
}

void upd(int ql, int qr, ll x, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr){
        quex(id, x); return;
    }
    if(qr <= l || r <= ql) return;
    relax(id);
    upd(ql, qr, x, l, mid, lid);
    upd(ql, qr, x, mid, r, rid);
    seg[id] = max(seg[lid], seg[rid]);
}

pll get(int ql, int qr, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr) return seg[id];
    if(qr <= l || r <= ql) return {0, 0};
    relax(id);
    return max(get(ql, qr, l, mid, lid), get(ql, qr, mid, r, rid));
}

int main(){
    fast_io;
    
    cin >> n;

    for(int i = 1; i < n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        adj[a].pb({b, {c, d}});
        adj[b].pb({a, {d, c}});
    }

    dfs3(1);
    int far = 0;
    for(int i = 1; i <= n; i++) if(h[far] <= h[i]) far = i;
    h[far] = 0; dfs(far);

    build(0, n);

    mark[far] = true;
    for(int i = 2; i <= n; i++){
        pll mx = get(0, n);
        res[i] = res[i-1] - mx.F;

        int v = mx.S;
        while(!mark[v]){
            upd(st[v], ft[v], -par[v].S);
            mark[v] = true; v = par[v].F;
        }
    }

    dfs1(1);
    res[1] = inf;
    dfs2(1);

    int q; cin >> q;
    for(int i = 1; i <= q; i++){
        int x; cin >> x;
        cout << res[x] << endl;
    }

}

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs1(int, int)':
designated_cities.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [u, w]: adj[v]){
      |              ^
designated_cities.cpp: In function 'void dfs2(int, int)':
designated_cities.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [u, w]: adj[v]){
      |              ^
designated_cities.cpp: In function 'void dfs3(int, int)':
designated_cities.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [u, w]: adj[v]){
      |              ^
designated_cities.cpp: In function 'void dfs(int, int)':
designated_cities.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto [u, w]: adj[v]){
      |              ^

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