oj.uz

Submission #624435

# Submission time Handle Problem Language Result Execution time Memory
624435 2022-08-08T09:15:53 Z radal Designated Cities (JOI19_designated_cities) C++17
16 / 100
 621 ms 69516 KB 
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr ll N = 2e5+10,mod = 998244353,inf = 1e9+10,lg = 20;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}

int par[N][lg],h[N],r,U,V,sz[N],tin[N],T,lc;
ll opt[N],d[N][2],up[N],sum,lz[N*4];
pair<ll,int> mx[N],seg[N*4];
vector<int> ti;
vector<pair<int,pll>> adj[N];

void pre(int v,int p){
    par[v][0] = p;
    tin[v] = T++;
    ti.pb(v);
    sz[v] = 1;
    for (auto u : adj[v]){
        if (u.X == p) continue;
        h[u.X] = h[v]+1;
        d[u.X][0] = d[v][0]+u.Y.X;
        d[u.X][1] = d[v][1]+u.Y.Y;
        pre(u.X,v);
        up[v] += up[u.X]+u.Y.Y;
        sz[v] += sz[u.X];
    }
}

void dfs(int v,int p){
    if (adj[v].size() == 1){
        mx[v] = {d[v][0],v};
        return;
    }
    ll a = -1,b = -1;
    pll pa = {-1,-1};
    for (auto u : adj[v]){
        if (u.X == p) continue;
        dfs(u.X,v);
        mx[v] = max(mx[v],mx[u.X]);
        if (mx[u.X].X > a){
            swap(pa.X,pa.Y);
            b = a;
            a = mx[u.X].X;
            pa.X = mx[u.X].Y;
        }
        else if (mx[u.X].X > b){
            b = mx[u.X].X;
            pa.Y = mx[u.X].Y;
        }
    }
    if (b == -1) return;
    ll calc = sum-up[r]+d[v][1]-d[v][0]-a-b+2*d[v][0];
    if (calc < opt[2]){
        opt[2] = calc;
        U = pa.X;
        V = pa.Y;
        lc = v;
    }
}

int lca(int u,int v){
    if (h[u] < h[v]) swap(u,v);
    repr(i,lg-1,0){
        if ((1 << i) <= h[u]-h[v]) u = par[u][i];
    }
    if (v == u) return v;
    repr(i,lg-1,0){
        if (par[v][i] != par[u][i]){
            v = par[v][i];
            u = par[u][i];
        }
    }
    return par[v][0];
}

void build(int l,int r,int v = 1){
    if (r-l == 1){
        int u = ti[l];
        if (u == U || u == V || adj[u].size() != 1){
            seg[v] = {0,u};
            return;
        }
        int lc2 = lca(lc,u);
        if (lc2 != lc){
            seg[v] = {d[u][0]-d[lc2][0]+d[lc][1]-d[lc2][1],u};
            return;
        }
        lc2 = lca(u,U);
        if (lc2 == lc) lc2 = lca(u,V);
        seg[v] = {d[u][0]-d[lc2][0],u};
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    build(l,m,u);
    build(m,r,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}

void upd(int l,int r,int s,int e,ll x,int v = 1){
    if (s == l && r == e){
        seg[v].X += x;
        lz[v] += x;
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    if (lz[v]){
        seg[u].X += lz[v];
        seg[u|1].X += lz[v];
        lz[u] += lz[v];
        lz[u|1] += lz[v];
        lz[v] = 0;
    }
    if (e <= m){
        upd(l,m,s,e,x,u);
        seg[v] = max(seg[u],seg[u|1]);
        return;
    }
    if (s >= m){
        upd(m,r,s,e,x,u|1);
        seg[v] = max(seg[u],seg[u|1]);
        return;
    }
    upd(l,m,s,m,x,u);
    upd(m,r,m,e,x,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}
int32_t main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    memset(opt,63,sizeof opt);
    int n;
    cin >> n;
    rep(i,1,n){
        int u,v,a,b;
        cin >> u >> v >> a >> b;
        adj[u].pb({v,{a,b}});
        adj[v].pb({u,{b,a}});
        sum += a;
        sum += b;
    }
    if (n == 2){
        int q;
        cin >> q;
        while (q--){
            int t;
            cin >> t;
            if (t == 2){
                cout << 0 << endl;
                continue;
            }
            if (t == 1){
                cout << min(adj[1][0].Y.Y,adj[1][0].Y.X) << endl;
                continue;
            }
        }
        return 0;
    }
    rep(i,1,n+1) if (adj[i].size() > 1) r = i;
    pre(r,0);
    rep(j,1,lg){
        rep(i,1,n+1){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    int leaf = 0;
    rep(i,1,n+1){
        opt[1] = min(opt[1],sum-up[r]+d[i][1]-d[i][0]);
        leaf += (adj[i].size() == 1);
    }
    dfs(r,0);
    set<int> st;
    st.insert(tin[U]);
    st.insert(tin[V]);
    int q;
    cin >> q;
    build(0,n);
    rep(i,3,leaf){
        pair<ll,int> p = seg[1];
        int v = seg[1].Y;
        upd(0,n,tin[v],tin[v]+1,-p.X);
        opt[i] = opt[i-1]-p.X;
        int lc2 = lca(v,lc);
        if (lc2 != lc){
            st.insert(tin[v]);
            int cur = par[lc][0],perv = lc;
            while (perv != lc2){
                upd(0,n,tin[cur],tin[cur]+sz[cur],-(d[lc][1]-d[cur][1]));
                upd(0,n,tin[perv],tin[perv]+sz[perv],d[lc][1]-d[cur][1]);
                perv = cur;
                cur = par[cur][0];
            }
            if (lc2 != r){
                upd(0,n,0,n,-(d[lc][1]-d[lc2][1]));
                upd(0,n,tin[lc2],tin[lc2]+sz[lc2],d[lc][1]-d[lc2][1]);
            }
            lc = lc2;
            continue;
        }
        auto it = st.lower_bound(tin[v]);
        int lc3 = -1;
        if (it != st.end()){
            int u = ti[*it];
            lc2 = lca(v,u);
        }
        if (it != st.begin()){
            it--;
            int u = ti[*it];
            lc3= lca(u,v);
        }
        if (lc3 != -1 && h[lc3] > h[lc2]) swap(lc3,lc2);
        st.insert(tin[v]);
        int cur = par[v][0];
        while(cur != lc2){
            upd(0,n,tin[cur],tin[cur]+sz[cur],-(d[cur][0]-d[par[cur][0]][0]));
            cur = par[cur][0];
        }
    }
    while (q--){
        int t;
        cin >> t;
        if (t >= leaf){
            cout << 0 << endl;
            continue;
        }
        cout << opt[t] << endl;
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 3 ms 6596 KB Output is correct
8 Incorrect 3 ms 6612 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 492 ms 57592 KB Output is correct
3 Correct 269 ms 61508 KB Output is correct
4 Correct 434 ms 57504 KB Output is correct
5 Correct 496 ms 57968 KB Output is correct
6 Correct 510 ms 59992 KB Output is correct
7 Correct 511 ms 59276 KB Output is correct
8 Correct 313 ms 68164 KB Output is correct
9 Correct 621 ms 60928 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 487 ms 57512 KB Output is correct
3 Correct 272 ms 60736 KB Output is correct
4 Correct 423 ms 57664 KB Output is correct
5 Correct 492 ms 57880 KB Output is correct
6 Correct 590 ms 60040 KB Output is correct
7 Correct 593 ms 62008 KB Output is correct
8 Correct 458 ms 69516 KB Output is correct
9 Correct 569 ms 60928 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 3 ms 6596 KB Output is correct
8 Incorrect 3 ms 6612 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 492 ms 57592 KB Output is correct
3 Correct 269 ms 61508 KB Output is correct
4 Correct 434 ms 57504 KB Output is correct
5 Correct 496 ms 57968 KB Output is correct
6 Correct 510 ms 59992 KB Output is correct
7 Correct 511 ms 59276 KB Output is correct
8 Correct 313 ms 68164 KB Output is correct
9 Correct 621 ms 60928 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 487 ms 57512 KB Output is correct
12 Correct 272 ms 60736 KB Output is correct
13 Correct 423 ms 57664 KB Output is correct
14 Correct 492 ms 57880 KB Output is correct
15 Correct 590 ms 60040 KB Output is correct
16 Correct 593 ms 62008 KB Output is correct
17 Correct 458 ms 69516 KB Output is correct
18 Correct 569 ms 60928 KB Output is correct
19 Correct 3 ms 6484 KB Output is correct
20 Incorrect 540 ms 57624 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 3 ms 6612 KB Output is correct
7 Correct 3 ms 6596 KB Output is correct
8 Incorrect 3 ms 6612 KB Output isn't correct
9 Halted 0 ms 0 KB -