Submission #1308501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308501		mohammadsam	Designated Cities (JOI19_designated_cities)	C++20	0 / 100	2097 ms	45256 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=2,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=2,int r=n+1){
    if(e <= s || e <= l || r <= s) return ;
    if(s <= l && r <= e){
        shift(u,v);
        return;
    }
    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]);
}
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);
    for(int j = 2;j <= n;j++){
        int v = ind[seg[1].mx.sec];
        while(!mark[v]){
            now += parw[v];
            update(st[v],ft[v],-parw[v]);
            mark[v] = 1;
            v = par[v];
        }
        dp[j] = min(dp[j],sum - now);
    }
}
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});
    }
    fill(dp,dp+n+1,inf);
    for(int i =1 ;i <= n;i++) solve(i);
    cin >> q;
    for(int j = 1;j <= q;j++){
        int d;
        cin >> d;
        cout << dp[d] << endl;
    }
    return 0;
}

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