oj.uz

Submission #710240

# Submission time Handle Problem Language Result Execution time Memory
710240 2023-03-15T05:59:26 Z victor_gao Designated Cities (JOI19_designated_cities) C++17
100 / 100
 498 ms 73724 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,dp[N],ans[N],mx[N],len[N],pos[N],total=0,s;
int fa[N],cost[N],in[N],out[N],dep[N],t=0;
bool vis[N];
vector<pair<int,pii> >g[N];
vector<int>path;
void dfs1(int p,int lp){
    pos[p]=p;
    for (auto [i,c]:g[p]){
        if (i!=lp){
            dfs1(i,p);
            dp[p]=dp[p]+dp[i]+c.y;
            mx[p]=max(mx[p],mx[i]+c.x);
        }
    }
}
void dfs2(int p,int lp,int val){
    dp[p]=(dp[p]+dp[lp]+val);
    ans[1]=min(ans[1],total-dp[p]);
    if (ans[2]>total-dp[p]-len[p]){
        ans[2]=total-dp[p]-len[p];
        s=p;
    }
    for (auto [i,c]:g[p]){
        if (i!=lp){
            dp[p]=dp[p]-dp[i]-c.y;
            dfs2(i,p,c.x);
            dp[p]=dp[p]+dp[i]+c.y;
        }
    }
    dp[p]=(dp[p]-dp[lp]-val);
}
void dfs3(int p,int lp,int up){
    int mx1=0,mx2=0;
    len[p]=max(mx[p],up);
    for (auto [i,c]:g[p]){
        if (i!=lp){
            mx2=max(mx2,mx[i]+c.x);
            if (mx2>mx1) swap(mx1,mx2);
        }
    }
    for (auto [i,c]:g[p]){
        if (i!=lp){
            int use=(mx[i]+c.x==mx1) ? mx2 : mx1;
            dfs3(i,p,max(up,use)+c.y);
        }
    }
}
void dfs4(int p,int lp,int cs){
    cost[p]=cs; fa[p]=lp;
    in[p]=++t; dep[p]=dep[lp]+cs;
    path.push_back(p);
    for (auto [i,c]:g[p]){
        if (i!=lp)
            dfs4(i,p,c.x);
    }
    out[p]=t;
}
struct segtree{
    pii seg[4*N];
    int tag[4*N];
    void add_tag(int i,int val){  seg[i].x+=val; tag[i]+=val; }
    void push(int i){
        if (tag[i]){
            add_tag(2*i,tag[i]); add_tag(2*i+1,tag[i]);
            tag[i]=0;
        }
    }
    void build(int l,int r,int i){
        if (l==r){
            seg[i]={dep[path[l-1]],path[l-1]};
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,2*i); build(mid+1,r,2*i+1);
        seg[i]=max(seg[2*i],seg[2*i+1]);
    }
    void modify(int l,int r,int i,int ll,int rr,int val){
        if (ll<=l&&rr>=r){
            add_tag(i,val);
            return;
        }
        int mid=(l+r)>>1; push(i);
        if (rr<=mid) modify(l,mid,2*i,ll,rr,val);
        else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,val);
        else {
            modify(l,mid,2*i,ll,rr,val);
            modify(mid+1,r,2*i+1,ll,rr,val);
        }
        seg[i]=max(seg[2*i],seg[2*i+1]);
    }
}seg;
void walk(int a){
    while (!vis[a]){
        vis[a]=1;
        seg.modify(1,n,1,in[a],out[a],-cost[a]);
        a=fa[a];
    }
}
signed main(){
    fast
    cin>>n;
    for (int i=0;i<=n;i++)
        ans[i]=1e18;
    for (int i=1;i<n;i++){
        int a,b,c,d; cin>>a>>b>>c>>d;
        total=(total+c+d);
        g[a].push_back({b,{c,d}});
        g[b].push_back({a,{d,c}});
    }
    dfs1(1,0);
    dfs3(1,0,0);
    dfs2(1,0,0);
    dfs4(s,0,0);
    seg.build(1,n,1);
    vis[s]=1;
    for (int i=2;i<=n;i++){
        pii now=seg.seg[1];
        if (i>2) ans[i]=ans[i-1]-now.x;
        walk(now.y);
    }
    int q; cin>>q;
    while (q--){
        int c; cin>>c;
        cout<<ans[c]<<'\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17620 KB Output is correct
2 Correct 9 ms 17528 KB Output is correct
3 Correct 9 ms 17620 KB Output is correct
4 Correct 8 ms 17620 KB Output is correct
5 Correct 8 ms 17620 KB Output is correct
6 Correct 7 ms 17620 KB Output is correct
7 Correct 8 ms 17568 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 8 ms 17616 KB Output is correct
10 Correct 8 ms 17620 KB Output is correct
11 Correct 10 ms 17620 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17620 KB Output is correct
2 Correct 382 ms 52284 KB Output is correct
3 Correct 419 ms 65072 KB Output is correct
4 Correct 356 ms 52260 KB Output is correct
5 Correct 355 ms 53040 KB Output is correct
6 Correct 381 ms 54168 KB Output is correct
7 Correct 335 ms 52884 KB Output is correct
8 Correct 459 ms 65556 KB Output is correct
9 Correct 284 ms 50536 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17620 KB Output is correct
2 Correct 426 ms 52252 KB Output is correct
3 Correct 441 ms 67256 KB Output is correct
4 Correct 372 ms 52288 KB Output is correct
5 Correct 382 ms 52932 KB Output is correct
6 Correct 387 ms 54464 KB Output is correct
7 Correct 352 ms 52228 KB Output is correct
8 Correct 439 ms 60800 KB Output is correct
9 Correct 255 ms 50556 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17620 KB Output is correct
2 Correct 9 ms 17528 KB Output is correct
3 Correct 9 ms 17620 KB Output is correct
4 Correct 8 ms 17620 KB Output is correct
5 Correct 8 ms 17620 KB Output is correct
6 Correct 7 ms 17620 KB Output is correct
7 Correct 8 ms 17568 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 8 ms 17616 KB Output is correct
10 Correct 8 ms 17620 KB Output is correct
11 Correct 10 ms 17620 KB Output is correct
12 Correct 12 ms 17620 KB Output is correct
13 Correct 10 ms 18004 KB Output is correct
14 Correct 10 ms 18072 KB Output is correct
15 Correct 10 ms 18004 KB Output is correct
16 Correct 11 ms 17960 KB Output is correct
17 Correct 10 ms 18004 KB Output is correct
18 Correct 10 ms 18064 KB Output is correct
19 Correct 11 ms 18036 KB Output is correct
20 Correct 11 ms 18076 KB Output is correct
21 Correct 11 ms 18004 KB Output is correct
22 Correct 12 ms 17940 KB Output is correct
23 Correct 11 ms 18004 KB Output is correct
24 Correct 12 ms 18004 KB Output is correct
25 Correct 12 ms 18132 KB Output is correct
26 Correct 10 ms 18004 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17620 KB Output is correct
2 Correct 382 ms 52284 KB Output is correct
3 Correct 419 ms 65072 KB Output is correct
4 Correct 356 ms 52260 KB Output is correct
5 Correct 355 ms 53040 KB Output is correct
6 Correct 381 ms 54168 KB Output is correct
7 Correct 335 ms 52884 KB Output is correct
8 Correct 459 ms 65556 KB Output is correct
9 Correct 284 ms 50536 KB Output is correct
10 Correct 8 ms 17620 KB Output is correct
11 Correct 426 ms 52252 KB Output is correct
12 Correct 441 ms 67256 KB Output is correct
13 Correct 372 ms 52288 KB Output is correct
14 Correct 382 ms 52932 KB Output is correct
15 Correct 387 ms 54464 KB Output is correct
16 Correct 352 ms 52228 KB Output is correct
17 Correct 439 ms 60800 KB Output is correct
18 Correct 255 ms 50556 KB Output is correct
19 Correct 10 ms 17620 KB Output is correct
20 Correct 388 ms 52292 KB Output is correct
21 Correct 445 ms 73724 KB Output is correct
22 Correct 386 ms 57184 KB Output is correct
23 Correct 395 ms 58944 KB Output is correct
24 Correct 425 ms 57732 KB Output is correct
25 Correct 414 ms 58864 KB Output is correct
26 Correct 441 ms 57860 KB Output is correct
27 Correct 498 ms 58876 KB Output is correct
28 Correct 432 ms 60472 KB Output is correct
29 Correct 402 ms 59144 KB Output is correct
30 Correct 373 ms 58188 KB Output is correct
31 Correct 323 ms 59196 KB Output is correct
32 Correct 452 ms 67768 KB Output is correct
33 Correct 281 ms 56968 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17620 KB Output is correct
2 Correct 9 ms 17528 KB Output is correct
3 Correct 9 ms 17620 KB Output is correct
4 Correct 8 ms 17620 KB Output is correct
5 Correct 8 ms 17620 KB Output is correct
6 Correct 7 ms 17620 KB Output is correct
7 Correct 8 ms 17568 KB Output is correct
8 Correct 8 ms 17620 KB Output is correct
9 Correct 8 ms 17616 KB Output is correct
10 Correct 8 ms 17620 KB Output is correct
11 Correct 10 ms 17620 KB Output is correct
12 Correct 10 ms 17620 KB Output is correct
13 Correct 382 ms 52284 KB Output is correct
14 Correct 419 ms 65072 KB Output is correct
15 Correct 356 ms 52260 KB Output is correct
16 Correct 355 ms 53040 KB Output is correct
17 Correct 381 ms 54168 KB Output is correct
18 Correct 335 ms 52884 KB Output is correct
19 Correct 459 ms 65556 KB Output is correct
20 Correct 284 ms 50536 KB Output is correct
21 Correct 8 ms 17620 KB Output is correct
22 Correct 426 ms 52252 KB Output is correct
23 Correct 441 ms 67256 KB Output is correct
24 Correct 372 ms 52288 KB Output is correct
25 Correct 382 ms 52932 KB Output is correct
26 Correct 387 ms 54464 KB Output is correct
27 Correct 352 ms 52228 KB Output is correct
28 Correct 439 ms 60800 KB Output is correct
29 Correct 255 ms 50556 KB Output is correct
30 Correct 12 ms 17620 KB Output is correct
31 Correct 10 ms 18004 KB Output is correct
32 Correct 10 ms 18072 KB Output is correct
33 Correct 10 ms 18004 KB Output is correct
34 Correct 11 ms 17960 KB Output is correct
35 Correct 10 ms 18004 KB Output is correct
36 Correct 10 ms 18064 KB Output is correct
37 Correct 11 ms 18036 KB Output is correct
38 Correct 11 ms 18076 KB Output is correct
39 Correct 11 ms 18004 KB Output is correct
40 Correct 12 ms 17940 KB Output is correct
41 Correct 11 ms 18004 KB Output is correct
42 Correct 12 ms 18004 KB Output is correct
43 Correct 12 ms 18132 KB Output is correct
44 Correct 10 ms 18004 KB Output is correct
45 Correct 10 ms 17620 KB Output is correct
46 Correct 388 ms 52292 KB Output is correct
47 Correct 445 ms 73724 KB Output is correct
48 Correct 386 ms 57184 KB Output is correct
49 Correct 395 ms 58944 KB Output is correct
50 Correct 425 ms 57732 KB Output is correct
51 Correct 414 ms 58864 KB Output is correct
52 Correct 441 ms 57860 KB Output is correct
53 Correct 498 ms 58876 KB Output is correct
54 Correct 432 ms 60472 KB Output is correct
55 Correct 402 ms 59144 KB Output is correct
56 Correct 373 ms 58188 KB Output is correct
57 Correct 323 ms 59196 KB Output is correct
58 Correct 452 ms 67768 KB Output is correct
59 Correct 281 ms 56968 KB Output is correct
60 Correct 12 ms 17620 KB Output is correct
61 Correct 456 ms 61284 KB Output is correct
62 Correct 456 ms 73156 KB Output is correct
63 Correct 439 ms 59984 KB Output is correct
64 Correct 438 ms 61632 KB Output is correct
65 Correct 432 ms 60224 KB Output is correct
66 Correct 463 ms 61684 KB Output is correct
67 Correct 408 ms 60220 KB Output is correct
68 Correct 406 ms 61744 KB Output is correct
69 Correct 452 ms 63056 KB Output is correct
70 Correct 443 ms 61792 KB Output is correct
71 Correct 412 ms 60980 KB Output is correct
72 Correct 396 ms 62644 KB Output is correct
73 Correct 469 ms 68868 KB Output is correct
74 Correct 315 ms 61208 KB Output is correct