제출 #487965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487965		balbit	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	729 ms	77152 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;

vector<pii> g[maxn]; // to, value
int up[maxn], updown[maxn], par[maxn];
ll sigup[maxn];

pii deep[maxn]; // dep, where
int dep[maxn];
ll RT = inf;
int p1, p2;
ll all[maxn], L[maxn], R[maxn];


void dfs1(int v, int p) {
    par[v] = p;
    for (pii u : g[v]) {
        if (u.f != p) {
            updown[u.f] = u.s;
            dfs1(u.f, v);
        }
        else up[v] = u.s;
    }
}

void dfs2(int v, int p) {
    for (pii u : g[v]) {
        if (u.f != p) {
            dep[u.f] = dep[v] + up[u.f];
            dfs2(u.f, v);
            sigup[v] += sigup[u.f] + up[u.f];
        }
    }
}

void dfs3(int v, int p) {
    if (p != -1) all[v] = all[p] - up[v] + updown[v];
    else all[v] = sigup[v];

    vector<pii>here; here.pb({dep[v], v});
    for (pii u : g[v]) {
        if (u.f != p) {
            dfs3(u.f,v);
            here.pb(deep[u.f]);
        }
    }
    sort(ALL(here), greater<pii>());
    if (SZ(here) > 1) {
        ll df = all[v] - here[0].f - here[1].f + dep[v]*2;
        bug(here[0].f, here[1].f, here[0].s, here[1].s);
        if (df < RT) {
            RT = df;
            p1 = here[0].s; p2 = here[1].s;
        }
    }
    deep[v] = here[0];
}

pii s[maxn*4];
ll tg[maxn*4];
bool rem[maxn];

void push(int o, int l, int r){
    if (tg[o]) {
        s[o].f += tg[o];
        if (l!=r) {
            tg[o*2] += tg[o];
            tg[o*2+1] += tg[o];
        }
        tg[o] = 0;
    }
}
void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l>R || r<L) return;
    if (l >= L && r <= R) {
        tg[o] += v;
        push(o,l,r);
        return;
    }
    int mid = (l+r)/2;
    MO(L,R,v,o*2,l,mid);
    MO(L,R,v,o*2+1,mid+1,r);
    s[o] = max(s[o*2], s[o*2+1]);
}


void MOpt(int p, pii v, int o=1, int l=0, int r=maxn-1) {
    if (l>p || r<p) return;
    if (l == r) {
        s[o] = v;
        return;
    }
    int mid = (l+r)/2;
    MOpt(p,v,o*2,l,mid);
    MOpt(p,v,o*2+1,mid+1,r);
    s[o] = max(s[o*2], s[o*2+1]);
}

int IT = 0;

void dfs4(int v, int p) {
    L[v] = R[v] = IT++;
    for (pii u : g[v]) {
        if (u.f != p) {
            dfs4(u.f,v);
            R[v] = R[u.f];
        }
    }
}

ll ans[maxn];

void clr(int v) {
    while (!rem[v]) {
        rem[v] = 1;
        int p = par[v];
        MO(L[v], R[v], -up[v]);
        v = p;
    }
}

signed main(){
    IOS();
    int n; cin>>n;
    REP(i,n-1) {
        int a,b,c,d; cin>>a>>b>>c>>d; swap(c,d);
        g[a].pb({b,c});
        g[b].pb({a,d});
    }

    dfs1(1,-1); dfs2(1,-1); dfs3(1,-1);

    memset(ans, 0x3f, sizeof ans);

    REP1(i,n) {
        bug(i, up[i], dep[i], sigup[i], all[i]);
        MN(ans[1], all[i]);
    }

    bug(RT, p1, p2);
    ans[2] = RT;

    dep[p1] = up[p1] = 0;

    dfs1(p1, -1); dfs2(p1, -1); dfs4(p1, -1);
    rem[p1] = 1;

    REP1(i,n) {
        bug(i, L[i], dep[i], up[i]);
        MOpt(L[i], {dep[i], i});
    }

    bug(s[1].f, s[1].s, dep[p2]);
    clr(p2);


    for (int k = 3; k<=n; ++k) {
        pii hi = s[1];
        bug (hi.f, hi.s);
        RT -= hi.f;
        clr(hi.s);
        ans[k] = RT;
    }

    int qq; cin>>qq;
    while (qq--) {
        int x; cin>>x;
        cout<<ans[x]<<endl;
    }





}

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