oj.uz

Submission #1030023

# Submission time Handle Problem Language Result Execution time Memory
1030023 2024-07-21T16:20:57 Z Alish Designated Cities (JOI19_designated_cities) C++14
16 / 100
 483 ms 72532 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;
        temp-=seg[0].F;
        while(!vis[v]){
            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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Incorrect 4 ms 18264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 296 ms 57568 KB Output is correct
3 Correct 452 ms 72532 KB Output is correct
4 Correct 249 ms 55840 KB Output is correct
5 Correct 224 ms 57116 KB Output is correct
6 Correct 295 ms 62280 KB Output is correct
7 Correct 256 ms 56240 KB Output is correct
8 Correct 483 ms 71520 KB Output is correct
9 Correct 153 ms 54936 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 290 ms 57548 KB Output is correct
3 Correct 422 ms 72004 KB Output is correct
4 Correct 252 ms 56148 KB Output is correct
5 Correct 238 ms 57148 KB Output is correct
6 Correct 289 ms 62288 KB Output is correct
7 Correct 123 ms 55940 KB Output is correct
8 Correct 404 ms 68352 KB Output is correct
9 Correct 143 ms 55320 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Incorrect 4 ms 18264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Correct 296 ms 57568 KB Output is correct
3 Correct 452 ms 72532 KB Output is correct
4 Correct 249 ms 55840 KB Output is correct
5 Correct 224 ms 57116 KB Output is correct
6 Correct 295 ms 62280 KB Output is correct
7 Correct 256 ms 56240 KB Output is correct
8 Correct 483 ms 71520 KB Output is correct
9 Correct 153 ms 54936 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 290 ms 57548 KB Output is correct
12 Correct 422 ms 72004 KB Output is correct
13 Correct 252 ms 56148 KB Output is correct
14 Correct 238 ms 57148 KB Output is correct
15 Correct 289 ms 62288 KB Output is correct
16 Correct 123 ms 55940 KB Output is correct
17 Correct 404 ms 68352 KB Output is correct
18 Correct 143 ms 55320 KB Output is correct
19 Correct 4 ms 18012 KB Output is correct
20 Incorrect 239 ms 57772 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18008 KB Output is correct
2 Incorrect 4 ms 18264 KB Output isn't correct
3 Halted 0 ms 0 KB -