Submission #105012

#	Time	Username	Problem	Language	Result	Execution time	Memory
105012		minhtung0404	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	794 ms	76408 KiB

designated_cities

//https://oj.uz/problem/view/JOI19_designated_cities

#include<bits/stdc++.h>
#define int long long
const int N = 2e5 + 5;
const long long inf = 1e18;
using namespace std;

typedef pair <long long, long long> ii;
typedef pair <int, ii> iii;

vector <iii> G[N];

ii trace[N][3], it[N << 2], root;
int lazy[N << 2];
int n, q, d[N], f[N], p[N], st[N], en[N], node[N], cnt, ans[N];
long long dp[N][4];
bool dead[N];

bool up(long long&a, long long b){
    if (a <= b) return false;
    a = b;
    return true;
}

void dfs(int u, int p){
    dp[u][0] = 0; dp[u][1] = dp[u][2] = dp[u][3] = inf;
    for (auto P : G[u]){
        int v = P.first, a = P.second.first, b = P.second.second;
        if (v == p) continue;
        dfs(v, u);
        dp[u][3] = min(dp[u][3] + dp[v][0] + a, dp[u][0] + dp[v][3] + b);
        dp[u][2] += dp[v][0] + a;
        if (up(dp[u][2], dp[u][1] + dp[v][1])) trace[u][2] = ii(trace[u][1].first, trace[v][1].first);
        if (up(dp[u][2], dp[u][0] + dp[v][2] + b)) trace[u][2] = trace[v][2];
        dp[u][1] += dp[v][0] + a;
        if (up(dp[u][1], dp[u][0] + dp[v][1])) trace[u][1] = trace[v][1];
        dp[u][0] += dp[v][0] + a;
    }
    dp[u][3] = min(dp[u][3], dp[u][0]);
    if (up(dp[u][2], dp[u][1])) trace[u][2] = ii(u, trace[u][1].first);
    if (up(dp[u][1], dp[u][0])) trace[u][1] = ii(u, 0);
}

void redfs(int u){
    st[u] = ++cnt; node[cnt] = u;
    for (auto P : G[u]){
        int v = P.first, a = P.second.first, b = P.second.second;
        if (v == p[u]) continue;
        d[v] = d[u] + a;
        p[v] = u; f[v] = a;
        redfs(v);
    }
    en[u] = cnt;
}

void init(int i, int l, int r){
    if (l == r){
        it[i] = ii(d[node[l]], node[l]);
        return;
    }
    int mid = (l + r) >> 1;
    init(i << 1, l, mid); init(i << 1 | 1, mid+1, r);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void dolazy(int i, int l, int r){
    if (!lazy[i]) return;
    if (l != r){
        lazy[i << 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
    }
    it[i].first -= lazy[i];
    lazy[i] = 0;
}

void update(int i, int l, int r, int L, int R, int val){
    dolazy(i, l, r);
    if (L > r || l > R) return;
    if (L <= l && r <= R){
        lazy[i] = val;
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, L, R, val); update(i << 1 | 1, mid+1, r, L, R, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void Erase(int u){
    int cur = u;
    while (u && dead[u] == false){
        dead[u] = true;
        update(1, 1, n, st[u], en[u], f[u]);
        u = p[u];
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 2; i <= n; i++){
        int u, v, a, b; cin >> u >> v >> a >> b;
        G[u].push_back(iii(v, ii(a, b)));
        G[v].push_back(iii(u, ii(b, a)));
    }
    dfs(1, 1);
    root = trace[1][2]; ans[1] = dp[1][3]; ans[2] = dp[1][2];
    redfs(root.first);
    init(1, 1, n);
    Erase(root.second);
    for (int i = 3; i <= n; i++){
        ans[i] = ans[i-1] - it[1].first;
        Erase(it[1].second);
    }
    cin >> q;
    while (q--){
        int x;
        cin >> x;
        cout << ans[x] << "\n";
    }
}

Compilation message (stderr)

designated_cities.cpp: In function 'void redfs(long long int)':
designated_cities.cpp:48:46: warning: unused variable 'b' [-Wunused-variable]
         int v = P.first, a = P.second.first, b = P.second.second;
                                              ^
designated_cities.cpp: In function 'void Erase(long long int)':
designated_cities.cpp:91:9: warning: unused variable 'cur' [-Wunused-variable]
     int cur = u;
         ^~~

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