oj.uz

Submission #624422

# Submission time Handle Problem Language Result Execution time Memory
624422 2022-08-08T08:53:22 Z radal Designated Cities (JOI19_designated_cities) C++17
16 / 100
 722 ms 75724 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[perv][1]-d[cur][1]));
                upd(0,n,tin[perv],tin[perv]+sz[perv],d[perv][1]-d[cur][1]);
                perv = cur;
                cur = par[cur][0];
            }
            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 4 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Incorrect 4 ms 6576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6576 KB Output is correct
2 Correct 670 ms 57912 KB Output is correct
3 Correct 466 ms 61964 KB Output is correct
4 Correct 555 ms 58036 KB Output is correct
5 Correct 656 ms 58264 KB Output is correct
6 Correct 694 ms 60504 KB Output is correct
7 Correct 667 ms 59836 KB Output is correct
8 Correct 514 ms 68544 KB Output is correct
9 Correct 722 ms 61288 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 712 ms 57860 KB Output is correct
3 Correct 490 ms 66992 KB Output is correct
4 Correct 571 ms 62568 KB Output is correct
5 Correct 656 ms 64124 KB Output is correct
6 Correct 712 ms 66328 KB Output is correct
7 Correct 719 ms 68168 KB Output is correct
8 Correct 641 ms 75724 KB Output is correct
9 Correct 708 ms 67068 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 4 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Incorrect 4 ms 6576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6576 KB Output is correct
2 Correct 670 ms 57912 KB Output is correct
3 Correct 466 ms 61964 KB Output is correct
4 Correct 555 ms 58036 KB Output is correct
5 Correct 656 ms 58264 KB Output is correct
6 Correct 694 ms 60504 KB Output is correct
7 Correct 667 ms 59836 KB Output is correct
8 Correct 514 ms 68544 KB Output is correct
9 Correct 722 ms 61288 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 712 ms 57860 KB Output is correct
12 Correct 490 ms 66992 KB Output is correct
13 Correct 571 ms 62568 KB Output is correct
14 Correct 656 ms 64124 KB Output is correct
15 Correct 712 ms 66328 KB Output is correct
16 Correct 719 ms 68168 KB Output is correct
17 Correct 641 ms 75724 KB Output is correct
18 Correct 708 ms 67068 KB Output is correct
19 Correct 3 ms 6484 KB Output is correct
20 Incorrect 677 ms 63752 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 4 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Incorrect 4 ms 6576 KB Output isn't correct
5 Halted 0 ms 0 KB -