제출 #1290025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290025		Tymond	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	347 ms	50464 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

struct Node{
    ll best, lazy;
    int bestId;
    Node(){
        best = lazy = 0LL;
        bestId = 0;
    }

    Node(ll b1, ll l, int b2){
        best = b1;
        lazy = l;
        bestId = b2;
    }
};

const int MAXN = 2e5 + 7;
const int BASE = (1 << 18);
Node tree[2 * BASE + 7];
vector<pair<int, pii>> g[MAXN];
ll goingUp[MAXN];
ll sumForOne[MAXN];
int in[MAXN];
int inF[MAXN];
int out[MAXN];
int parent[MAXN];
int used[MAXN];
ll A[MAXN];
ll jumpUp[MAXN];
ll ans[MAXN];
ll sum;
int n, q, timer;
ll now;
pii best;

void dfsInit(int v, int p){
    for(auto ele : g[v]){
        if(ele.fi == p){
            continue;
        }
        jumpUp[ele.fi] = ele.se.fi;
        goingUp[v] += ele.se.se;
        dfsInit(ele.fi, v);
        goingUp[v] += goingUp[ele.fi];
    }
}

void dfs1(int v, int p, ll up = 0LL){
    sumForOne[v] = goingUp[v] + up;
    for(auto ele : g[v]){
        if(ele.fi == p){
            continue;
        }
        dfs1(ele.fi, v, up + goingUp[v] - goingUp[ele.fi] - ele.se.se + ele.se.fi);
    }
}

void dfs2(int v, int p, ll up = 0LL){
    A[v] = up;
    used[v] = 0;
    parent[v] = p;
    in[v] = timer++;
    inF[in[v]] = v;
    for(auto ele : g[v]){
        if(ele.fi == p){
            continue;
        }
        jumpUp[ele.fi] = ele.se.fi;
        dfs2(ele.fi, v, up + ele.se.fi);
    }
    out[v] = timer - 1;
}

Node merge(Node& a, Node& b){
    if(a.best >= b.best){
        return Node(a.best, 0LL, a.bestId);
    }
    return Node(b.best, 0LL, b.bestId);
}

void Push(int v){
    for(int j = 0; j < 2; j++){
        tree[2 * v + j].lazy += tree[v].lazy;
        tree[2 * v + j].best += tree[v].lazy;
    }
    tree[v].lazy = 0LL;
}

void upd(int v, int l, int p, int a, int b, ll val){
    if(p < a || b < l){
        return;
    }

    if(a <= l && p <= b){
        tree[v].best += val;
        tree[v].lazy += val;
        return;
    }
    Push(v);
    int mid = (l + p) / 2;
    upd(2 * v, l ,mid, a, b, val);
    upd(2 * v + 1, mid + 1, p, a,b, val);
    tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}

void dfsRecalc(int v, int p){
    if(v != p && !used[v]){
        A[v] = jumpUp[v] + A[p];
    }
    for(auto ele : g[v]){
        if(ele.fi != p){
            dfsRecalc(ele.fi, v);
        }
    }
}

pair<ll, int> dfsPair(int v, int p){
    pair<pair<ll, int>, pair<ll, int>> e = mp(mp(0LL, v), mp(-1LL, -1));
    for(auto ele : g[v]){
        if(ele.fi == p){
            continue;
        }

        pair<ll, int> x = dfsPair(ele.fi, v);
        if(x.fi >= e.fi.fi){
            swap(e.fi, e.se);
            e.fi = x;
        }else if(x.fi > e.se.fi){
            e.se = x;
        }
    }
    // debug(v);
    // debug(e);
    // debug(jumpUp[v]);
    if(e.se.fi == -1LL){
        e.fi.fi += jumpUp[v];
        return e.fi;
    }

    if(now < sumForOne[v] + e.fi.fi + e.se.fi){
        now = sumForOne[v] + e.fi.fi + e.se.fi;
        best = mp(e.fi.se, e.se.se);
    }
    e.fi.fi += jumpUp[v];
    return e.fi;
}   

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
        
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        g[a].pb(mp(b, mp(c, d)));
        g[b].pb(mp(a, mp(d, c)));
        sum += (c + d);
    }

    //policz wynik
    int root;
    dfsInit(1, 1);
    dfs1(1, 1);
    root = 1;
    for(int i = 2; i <= n; i++){
        if(sumForOne[i] > sumForOne[root]){
            root = i;
        }
    }
    ans[1] = sumForOne[root];

    //teraz znajdź rozw dla e = 2
    now = 0LL;
    best = mp(-1, -1);
    dfsPair(1, 1);
    ans[2] = now;
   // debug(best);
    root = best.fi;
    timer = 0;
    dfs2(root, root);
    while(best.se != root){
        used[best.se] = 1;
        A[best.se] = 0LL;
        best.se = parent[best.se];
    }
    dfsRecalc(root, root);

    for(int i = 1; i <= n; i++){
        tree[in[i] + BASE] = Node(A[i], 0LL, i);
    }

    for(int i = BASE - 1; i >= 1; i--){
        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    used[root] = 1;
    for(int i = 3; i <= n; i++){
        ans[i] = ans[i - 1] + tree[1].best;
        int v = tree[1].bestId;

        ll curr = tree[1].best;
        int pre = -1;
        while(!used[v]){
            used[v] = 1;
            //aktualizuj drzewo
            upd(1, 0, BASE - 1, in[v], out[v], -curr);
            if(pre != -1){
                upd(1, 0, BASE - 1, in[pre], out[pre], curr);
            }

            curr -= jumpUp[v];
            pre = v;
            v = parent[v];
        }
    }

    cin >> q;
    while(q--){
        int e;
        cin >> e;
        cout << (ll)sum - ans[e] << '\n';
    }

    return 0;
}

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