Submission #1308564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308564		mohammadsam	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	1241 ms	68212 KiB

designated_cities

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 1e17 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n,q;
vector<pii> g[N];
int dp[N],dis[N];
int par[N],st[N],ft[N],ind[N],tim = 1;
int parw[N];
int sum =0,now= 0;
void dfs(int u,int p,int w=0){
    sum += w;
    par[u] = p;
    parw[u] =w;
    dis[u] = (u == p ? 0 : dis[p] + w);
    st[u] = tim++;
    ind[st[u]] = u;
    for(auto h : g[u]){
        if(h.fi != p){
            dfs(h.fi,u,h.sec);
        }
    }
    ft[u] = tim;
}
struct node{
    pii mx;
    int lazy;
    node(pii mx,int lazy): mx(mx),lazy(lazy){}
    node(){}
} seg[N<<2];
node merge(const node& a,const node& b){
    return node(max(a.mx,b.mx),0);
}
void shift(int u,int v){
    seg[u].mx.fi += v;
    seg[u].lazy += v;
}
void relax(int u){
    shift(lid,seg[u].lazy);
    shift(rid,seg[u].lazy);
    seg[u].lazy = 0;
}
void build(int u=1,int l=1,int r=n+1){
    if(r-l==1){
        seg[u].mx = {dis[ind[l]],l};
        seg[u].lazy = 0;
        return ;
    }
    int mid = (l+r)>>1;
    build(lid,l,mid);
    build(rid,mid,r);
    seg[u] = merge(seg[lid],seg[rid]);
}
void update(int s,int e,int v,int u=1,int l=1,int r=n+1){
    if(e <= s || e <= l || r <= s) return ;
    if(s <= l && r <= e){
        shift(u,v);
        return;
    }
    relax(u);
    int mid = (l+r)>>1;
    update(s,e,v,lid,l,mid);
    update(s,e,v,rid,mid,r);
    seg[u] = merge(seg[lid],seg[rid]);
}
node get(int s,int e,int u=1,int l=1,int r=n+1){
    if(s <= l && r <= e) return seg[u];
    int mid = (l+r)>>1;
    relax(u);
    if(e <= mid) return get(s,e,lid,l,mid);
    if(s >= mid) return get(s,e,rid,mid,r);
    return merge(get(s,e,lid,l,mid),get(s,e,rid,mid,r));
}
bool mark[N];
void solve(int u){
    sum = now = 0;
    tim = 1;
    dfs(u,u);
    build();
    dp[1] = min(dp[1],sum);
    fill(mark,mark+n+2,0);
    mark[u] = 1;
    for(int j = 2;j <= n;j++){
        int v = ind[seg[1].mx.sec];
        now += seg[1].mx.fi;
        // cout << v << sep <<  seg[1].mx.fi << endl;
        while(!mark[v]){
            update(st[v],ft[v],-parw[v]);
            // cout << "marked " << v << endl;
            mark[v] = 1;
            v = par[v];
        }
        dp[j] = min(dp[j],sum - now);
    }
}
int S = 0;
int f[N];
int p2[N];
int hei[N];
void pre_dfs(int u,int p,int w =0){
    S += w;
    for(auto h : g[u]){
        if(h.fi != p) pre_dfs(h.fi,u,h.sec);
    }
}
void calc(int u,int p,int w1=0,int w2=0){
    if(u^p) f[u] = f[p] - w1 + w2;
    p2[u] = w2;
    hei[u] = (u == p ? 0 : hei[p] + w1 + w2);
    for(auto h : g[u]){
        if(h.fi != p){
            int w2 = 0;
            for(auto x : g[h.fi]){
                if(x.fi == u) w2 = x.sec;
            }
            calc(h.fi,u,h.sec,w2);
        }
    }
}

int ans = inf;
pii Best = {-1,-1};
void DFS(int u,int p){
    int v = seg[1].mx.second;
    int tmp = (-seg[1].mx.fi + f[u])/2;
    if(tmp <= ans){
        ans = tmp;
        Best = {u,v};
    }
    for(auto h : g[u]){
        if(h.fi != p){
            int W = h.sec + p2[h.fi];
            update(1,n+1,W);
            update(st[h.fi],ft[h.fi],-2*W);
            DFS(h.fi,u);
            update(st[h.fi],ft[h.fi],2*W);
            update(1,n+1,-W);
        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n;
    for(int i = 0 ;i < n -1;i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        g[a].pb({b,c});
        g[b].pb({a,d});
    }
    pre_dfs(1,1);
    f[1] = S;
    calc(1,1,0,0);
    int u = 0;
    f[0] = inf;
    for(int i = 1;i <= n;i++){
        if(f[i] < f[u]) u = i;
    }
    fill(dp,dp+n+1,inf);
    solve(u);
    sum = now =0 ;
    tim = 1;
    dfs(1,1);
    build();
    for(int i= 1 ;i <= n;i++){
        update(i,i+1,-get(i,i+1).mx.fi - f[ind[i]] + hei[i]);
    }
    DFS(1,1);
    solve(Best.fi);
    solve(Best.second);
    cin >> q;
    for(int j = 1;j <= q;j++){
        int d;
        cin >> d;
        cout << dp[d] << endl;
    }
    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