oj.uz

Submission #1030025

# Submission time Handle Problem Language Result Execution time Memory
1030025 2024-07-21T16:23:35 Z Alish Designated Cities (JOI19_designated_cities) C++17
100 / 100
 428 ms 74292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7;

const int N = 2e5+23;

vector<pll> g[N], gp[N];
ll h[N], dp[N], up[N];
int par[N];
pll seg[4*N];
ll lpz[4*N];
int st[N], ft[N], pos[N], tim;
int vis[N];
ll temp;
ll ans[N];
int n, q;
pll di;


void dfs0(int v, int p=0){//down
    for (auto pp: g[v]){
        ll u=pp.F, w=pp.S;
        if(u==p) continue;
        dp[1]+=w;
        dfs0(u, v);
    }
}

void dfs1(int v, int p=0){//up
    ans[1]=min(ans[1], dp[v]);
    for (auto pp: gp[v]){
        ll u=pp.F, w=pp.S;
        if(u==p) continue;
        dp[u]=dp[v]+w;
        dfs1(u, v);
    }
}

void dfs2(int v, int p=0){//diam
    di=max(di, Mp(h[v], 1ll*v));
    for (auto pp: g[v]){
        ll u=pp.F, w=pp.S;
        if(u==p) continue;
        h[u]=h[v]+w;
        dfs2(u, v);
    }
}
void dfs3(int v, int p=0){//st-ft...
    st[v]=tim++;
    pos[st[v]]=v;
    for (auto pp: g[v]){
        ll u=pp.F, w=pp.S;
        if(u==p) continue;
        h[u]=h[v]+w;
        temp+=w;
        par[u]=v;
        up[u]=w;
        dfs3(u, v);
    }
    ft[v]=tim;
}

void build(int l=0, int r=n, int ind=0){
    if(r-l==1){
        seg[ind]={h[pos[l]], pos[l]};
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}
void Shift(int l, int r, int ind){
    if(r-l==1) return;
    if(!lpz[ind]) return;
    seg[2*ind+1].F+=lpz[ind];
    seg[2*ind+2].F+=lpz[ind];
    lpz[2*ind+1]+=lpz[ind];
    lpz[2*ind+2]+=lpz[ind];
    lpz[ind]=0;
}
void upd(int lx, int rx, ll x, int l=0, int r=n, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return;
    if(lx<=l && rx>=r){
        seg[ind].F+=x;
        lpz[ind]+=x;
        return;
    }
    int mid=(r+l)>>1;
    upd(lx, rx, x, l, mid, 2*ind+1); upd(lx, rx, x, mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}

int main()
{
    fast_io
    cin>>n;
    for (int i=0; i<n-1; i++){
        int u, v, w1, w2;
        cin>>v>>u>>w1>>w2;
        g[v].pb({u, w1}); g[u].pb({v, w2});
        gp[v].pb({u, w2-w1});
        gp[u].pb({v, w1-w2});
    }
    dfs0(1);
    ans[1]=dp[1];
    dfs1(1);
    dfs2(1);
    h[di.S]=0;
    dfs3(di.S);
    build();
    vis[di.S]=1;
    for (int i=2; i<=n; i++){
        int v=seg[0].S;
        while(!vis[v]){
            temp-=up[v];
            vis[v]=1;
            upd(st[v], ft[v], -up[v]);
            v=par[v];
        }
        ans[i]=temp;
    }
    cin>>q;
    while(q--){
        int x; cin>>x;
        cout<<ans[x]<<endl;
    }

}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18008 KB Output is correct
2 Correct 2 ms 18008 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 5 ms 18108 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 4 ms 18012 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18008 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18012 KB Output is correct
2 Correct 336 ms 56992 KB Output is correct
3 Correct 403 ms 69460 KB Output is correct
4 Correct 361 ms 56920 KB Output is correct
5 Correct 271 ms 57072 KB Output is correct
6 Correct 291 ms 59220 KB Output is correct
7 Correct 276 ms 55812 KB Output is correct
8 Correct 428 ms 68948 KB Output is correct
9 Correct 249 ms 51736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18152 KB Output is correct
2 Correct 368 ms 53292 KB Output is correct
3 Correct 383 ms 65616 KB Output is correct
4 Correct 305 ms 53768 KB Output is correct
5 Correct 328 ms 53832 KB Output is correct
6 Correct 407 ms 58108 KB Output is correct
7 Correct 242 ms 52544 KB Output is correct
8 Correct 360 ms 65684 KB Output is correct
9 Correct 210 ms 55756 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18008 KB Output is correct
2 Correct 2 ms 18008 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 5 ms 18108 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 4 ms 18012 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18008 KB Output is correct
12 Correct 3 ms 18008 KB Output is correct
13 Correct 4 ms 18520 KB Output is correct
14 Correct 5 ms 18648 KB Output is correct
15 Correct 6 ms 18524 KB Output is correct
16 Correct 5 ms 18524 KB Output is correct
17 Correct 5 ms 18520 KB Output is correct
18 Correct 4 ms 18368 KB Output is correct
19 Correct 6 ms 18524 KB Output is correct
20 Correct 4 ms 18524 KB Output is correct
21 Correct 7 ms 18524 KB Output is correct
22 Correct 5 ms 18524 KB Output is correct
23 Correct 4 ms 18524 KB Output is correct
24 Correct 6 ms 18524 KB Output is correct
25 Correct 5 ms 18524 KB Output is correct
26 Correct 6 ms 18524 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18012 KB Output is correct
2 Correct 336 ms 56992 KB Output is correct
3 Correct 403 ms 69460 KB Output is correct
4 Correct 361 ms 56920 KB Output is correct
5 Correct 271 ms 57072 KB Output is correct
6 Correct 291 ms 59220 KB Output is correct
7 Correct 276 ms 55812 KB Output is correct
8 Correct 428 ms 68948 KB Output is correct
9 Correct 249 ms 51736 KB Output is correct
10 Correct 3 ms 18152 KB Output is correct
11 Correct 368 ms 53292 KB Output is correct
12 Correct 383 ms 65616 KB Output is correct
13 Correct 305 ms 53768 KB Output is correct
14 Correct 328 ms 53832 KB Output is correct
15 Correct 407 ms 58108 KB Output is correct
16 Correct 242 ms 52544 KB Output is correct
17 Correct 360 ms 65684 KB Output is correct
18 Correct 210 ms 55756 KB Output is correct
19 Correct 2 ms 18012 KB Output is correct
20 Correct 298 ms 53796 KB Output is correct
21 Correct 357 ms 72524 KB Output is correct
22 Correct 323 ms 58260 KB Output is correct
23 Correct 346 ms 60356 KB Output is correct
24 Correct 338 ms 59068 KB Output is correct
25 Correct 412 ms 60356 KB Output is correct
26 Correct 386 ms 59216 KB Output is correct
27 Correct 366 ms 59712 KB Output is correct
28 Correct 359 ms 61980 KB Output is correct
29 Correct 299 ms 60572 KB Output is correct
30 Correct 339 ms 58568 KB Output is correct
31 Correct 245 ms 58920 KB Output is correct
32 Correct 411 ms 69380 KB Output is correct
33 Correct 230 ms 59236 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18008 KB Output is correct
2 Correct 2 ms 18008 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 5 ms 18108 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 4 ms 18012 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18008 KB Output is correct
12 Correct 2 ms 18012 KB Output is correct
13 Correct 336 ms 56992 KB Output is correct
14 Correct 403 ms 69460 KB Output is correct
15 Correct 361 ms 56920 KB Output is correct
16 Correct 271 ms 57072 KB Output is correct
17 Correct 291 ms 59220 KB Output is correct
18 Correct 276 ms 55812 KB Output is correct
19 Correct 428 ms 68948 KB Output is correct
20 Correct 249 ms 51736 KB Output is correct
21 Correct 3 ms 18152 KB Output is correct
22 Correct 368 ms 53292 KB Output is correct
23 Correct 383 ms 65616 KB Output is correct
24 Correct 305 ms 53768 KB Output is correct
25 Correct 328 ms 53832 KB Output is correct
26 Correct 407 ms 58108 KB Output is correct
27 Correct 242 ms 52544 KB Output is correct
28 Correct 360 ms 65684 KB Output is correct
29 Correct 210 ms 55756 KB Output is correct
30 Correct 3 ms 18008 KB Output is correct
31 Correct 4 ms 18520 KB Output is correct
32 Correct 5 ms 18648 KB Output is correct
33 Correct 6 ms 18524 KB Output is correct
34 Correct 5 ms 18524 KB Output is correct
35 Correct 5 ms 18520 KB Output is correct
36 Correct 4 ms 18368 KB Output is correct
37 Correct 6 ms 18524 KB Output is correct
38 Correct 4 ms 18524 KB Output is correct
39 Correct 7 ms 18524 KB Output is correct
40 Correct 5 ms 18524 KB Output is correct
41 Correct 4 ms 18524 KB Output is correct
42 Correct 6 ms 18524 KB Output is correct
43 Correct 5 ms 18524 KB Output is correct
44 Correct 6 ms 18524 KB Output is correct
45 Correct 2 ms 18012 KB Output is correct
46 Correct 298 ms 53796 KB Output is correct
47 Correct 357 ms 72524 KB Output is correct
48 Correct 323 ms 58260 KB Output is correct
49 Correct 346 ms 60356 KB Output is correct
50 Correct 338 ms 59068 KB Output is correct
51 Correct 412 ms 60356 KB Output is correct
52 Correct 386 ms 59216 KB Output is correct
53 Correct 366 ms 59712 KB Output is correct
54 Correct 359 ms 61980 KB Output is correct
55 Correct 299 ms 60572 KB Output is correct
56 Correct 339 ms 58568 KB Output is correct
57 Correct 245 ms 58920 KB Output is correct
58 Correct 411 ms 69380 KB Output is correct
59 Correct 230 ms 59236 KB Output is correct
60 Correct 3 ms 18008 KB Output is correct
61 Correct 368 ms 62920 KB Output is correct
62 Correct 369 ms 74292 KB Output is correct
63 Correct 343 ms 61552 KB Output is correct
64 Correct 333 ms 63444 KB Output is correct
65 Correct 357 ms 62252 KB Output is correct
66 Correct 383 ms 63604 KB Output is correct
67 Correct 382 ms 62060 KB Output is correct
68 Correct 318 ms 63092 KB Output is correct
69 Correct 408 ms 65104 KB Output is correct
70 Correct 341 ms 63784 KB Output is correct
71 Correct 317 ms 61756 KB Output is correct
72 Correct 262 ms 62416 KB Output is correct
73 Correct 389 ms 71768 KB Output is correct
74 Correct 265 ms 64484 KB Output is correct