oj.uz

Submission #611841

# Submission time Handle Problem Language Result Execution time Memory
611841 2022-07-29T08:03:07 Z alireza_kaviani Designated Cities (JOI19_designated_cities) C++17
100 / 100
 620 ms 105456 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())
#define lc          id << 1
#define rc          lc | 1

const ll MAXN = 1e6 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , q , cost , root , timer , ans[MAXN] , H[MAXN] , st[MAXN] , fn[MAXN] , par[MAXN] , W[MAXN] , ind[MAXN] , mark[MAXN] , lz[MAXN << 2];
pll seg[MAXN << 2];
vector<pii> adj[MAXN] , g[MAXN];

void PreDFS(int v , int p = -1){
    ans[1] = min(ans[1] , H[v]);
    for(pii i : g[v]){
        int u = i.X , w = i.Y;
        if(u == p)  continue;
        H[u] = H[v] + w;
        PreDFS(u , v);
    }
}

void DistDFS(int v , int p = -1){
    ind[timer] = v;
    st[v] = timer++;
    for(pii i : adj[v]){
        int u = i.X , w = i.Y;
        if(u == p)  continue;
        cost += w;
        par[u] = v; W[u] = w;
        H[u] = H[v] + w;
        DistDFS(u , v);
    }
    fn[v] = timer;
}

void build(int id = 1 , int l = 0 , int r = n){
    if(r - l == 1){
        seg[id] = {H[ind[l]] , ind[l]};
        return;
    }
    int mid = l + r >> 1;
    build(lc , l , mid);
    build(rc , mid , r);
    seg[id] = max(seg[lc] , seg[rc]);
}

void shift(int id){
    seg[lc].X += lz[id]; lz[lc] += lz[id];
    seg[rc].X += lz[id]; lz[rc] += lz[id];
    lz[id] = 0;
}

void update(int ql , int qr , int x , int id = 1 , int l = 0 , int r = n){
    if(qr <= l || r <= ql)  return;
    if(ql <= l && r <= qr){
        seg[id].X += x;
        lz[id] += x;
        return;
    }
    shift(id);
    int mid = l + r >> 1;
    update(ql , qr , x , lc , l , mid);
    update(ql , qr , x , rc , mid , r);
    seg[id] = max(seg[lc] , seg[rc]);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> n;
    for(int i = 1 ; i < n ; i++){
        int v , u , w1 , w2;
        cin >> v >> u >> w1 >> w2;
        adj[v].push_back({u , w1});
        adj[u].push_back({v , w2});
        g[v].push_back({u , w2 - w1});
        g[u].push_back({v , w1 - w2});
    }

    PreDFS(1);
    DistDFS(1);
    ans[1] += cost;
    root = max_element(H , H + MAXN) - H;
    H[root] = cost = timer = 0;
    DistDFS(root);
    mark[root] = 1;

    build();
    for(int i = 2 ; i <= n ; i++){
        int v = seg[1].Y;
        while(!mark[v]){
            cost -= W[v];
            update(st[v] , fn[v] , -W[v]);
            mark[v] = 1;
            v = par[v];
        }
        ans[i] = cost;
    }
    
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        cout << ans[x] << endl;
    }

    return 0;
}
/*

*/

Compilation message

designated_cities.cpp: In function 'void build(int, int, int)':
designated_cities.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
designated_cities.cpp: In function 'void update(int, int, int, int, int, int)':
designated_cities.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47376 KB Output is correct
2 Correct 28 ms 47360 KB Output is correct
3 Correct 31 ms 47296 KB Output is correct
4 Correct 35 ms 47316 KB Output is correct
5 Correct 27 ms 47316 KB Output is correct
6 Correct 30 ms 47280 KB Output is correct
7 Correct 26 ms 47272 KB Output is correct
8 Correct 27 ms 47360 KB Output is correct
9 Correct 28 ms 47264 KB Output is correct
10 Correct 26 ms 47308 KB Output is correct
11 Correct 26 ms 47272 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47380 KB Output is correct
2 Correct 521 ms 93184 KB Output is correct
3 Correct 531 ms 103648 KB Output is correct
4 Correct 522 ms 91804 KB Output is correct
5 Correct 536 ms 93224 KB Output is correct
6 Correct 499 ms 94728 KB Output is correct
7 Correct 467 ms 93392 KB Output is correct
8 Correct 558 ms 103248 KB Output is correct
9 Correct 400 ms 94304 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47376 KB Output is correct
2 Correct 517 ms 93088 KB Output is correct
3 Correct 504 ms 103660 KB Output is correct
4 Correct 445 ms 91788 KB Output is correct
5 Correct 481 ms 93052 KB Output is correct
6 Correct 520 ms 95136 KB Output is correct
7 Correct 371 ms 93852 KB Output is correct
8 Correct 594 ms 100656 KB Output is correct
9 Correct 452 ms 93912 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47376 KB Output is correct
2 Correct 28 ms 47360 KB Output is correct
3 Correct 31 ms 47296 KB Output is correct
4 Correct 35 ms 47316 KB Output is correct
5 Correct 27 ms 47316 KB Output is correct
6 Correct 30 ms 47280 KB Output is correct
7 Correct 26 ms 47272 KB Output is correct
8 Correct 27 ms 47360 KB Output is correct
9 Correct 28 ms 47264 KB Output is correct
10 Correct 26 ms 47308 KB Output is correct
11 Correct 26 ms 47272 KB Output is correct
12 Correct 31 ms 47316 KB Output is correct
13 Correct 36 ms 47812 KB Output is correct
14 Correct 33 ms 47816 KB Output is correct
15 Correct 33 ms 47796 KB Output is correct
16 Correct 38 ms 47840 KB Output is correct
17 Correct 38 ms 47804 KB Output is correct
18 Correct 31 ms 47756 KB Output is correct
19 Correct 32 ms 47760 KB Output is correct
20 Correct 32 ms 47760 KB Output is correct
21 Correct 28 ms 47820 KB Output is correct
22 Correct 30 ms 47692 KB Output is correct
23 Correct 30 ms 47816 KB Output is correct
24 Correct 32 ms 47848 KB Output is correct
25 Correct 30 ms 47788 KB Output is correct
26 Correct 30 ms 47860 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47380 KB Output is correct
2 Correct 521 ms 93184 KB Output is correct
3 Correct 531 ms 103648 KB Output is correct
4 Correct 522 ms 91804 KB Output is correct
5 Correct 536 ms 93224 KB Output is correct
6 Correct 499 ms 94728 KB Output is correct
7 Correct 467 ms 93392 KB Output is correct
8 Correct 558 ms 103248 KB Output is correct
9 Correct 400 ms 94304 KB Output is correct
10 Correct 30 ms 47376 KB Output is correct
11 Correct 517 ms 93088 KB Output is correct
12 Correct 504 ms 103660 KB Output is correct
13 Correct 445 ms 91788 KB Output is correct
14 Correct 481 ms 93052 KB Output is correct
15 Correct 520 ms 95136 KB Output is correct
16 Correct 371 ms 93852 KB Output is correct
17 Correct 594 ms 100656 KB Output is correct
18 Correct 452 ms 93912 KB Output is correct
19 Correct 29 ms 47360 KB Output is correct
20 Correct 487 ms 93188 KB Output is correct
21 Correct 513 ms 103640 KB Output is correct
22 Correct 491 ms 91788 KB Output is correct
23 Correct 541 ms 93344 KB Output is correct
24 Correct 533 ms 91968 KB Output is correct
25 Correct 526 ms 93144 KB Output is correct
26 Correct 565 ms 92104 KB Output is correct
27 Correct 472 ms 93148 KB Output is correct
28 Correct 590 ms 94800 KB Output is correct
29 Correct 547 ms 93100 KB Output is correct
30 Correct 473 ms 92424 KB Output is correct
31 Correct 431 ms 93528 KB Output is correct
32 Correct 570 ms 100916 KB Output is correct
33 Correct 385 ms 94356 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47376 KB Output is correct
2 Correct 28 ms 47360 KB Output is correct
3 Correct 31 ms 47296 KB Output is correct
4 Correct 35 ms 47316 KB Output is correct
5 Correct 27 ms 47316 KB Output is correct
6 Correct 30 ms 47280 KB Output is correct
7 Correct 26 ms 47272 KB Output is correct
8 Correct 27 ms 47360 KB Output is correct
9 Correct 28 ms 47264 KB Output is correct
10 Correct 26 ms 47308 KB Output is correct
11 Correct 26 ms 47272 KB Output is correct
12 Correct 28 ms 47380 KB Output is correct
13 Correct 521 ms 93184 KB Output is correct
14 Correct 531 ms 103648 KB Output is correct
15 Correct 522 ms 91804 KB Output is correct
16 Correct 536 ms 93224 KB Output is correct
17 Correct 499 ms 94728 KB Output is correct
18 Correct 467 ms 93392 KB Output is correct
19 Correct 558 ms 103248 KB Output is correct
20 Correct 400 ms 94304 KB Output is correct
21 Correct 30 ms 47376 KB Output is correct
22 Correct 517 ms 93088 KB Output is correct
23 Correct 504 ms 103660 KB Output is correct
24 Correct 445 ms 91788 KB Output is correct
25 Correct 481 ms 93052 KB Output is correct
26 Correct 520 ms 95136 KB Output is correct
27 Correct 371 ms 93852 KB Output is correct
28 Correct 594 ms 100656 KB Output is correct
29 Correct 452 ms 93912 KB Output is correct
30 Correct 31 ms 47316 KB Output is correct
31 Correct 36 ms 47812 KB Output is correct
32 Correct 33 ms 47816 KB Output is correct
33 Correct 33 ms 47796 KB Output is correct
34 Correct 38 ms 47840 KB Output is correct
35 Correct 38 ms 47804 KB Output is correct
36 Correct 31 ms 47756 KB Output is correct
37 Correct 32 ms 47760 KB Output is correct
38 Correct 32 ms 47760 KB Output is correct
39 Correct 28 ms 47820 KB Output is correct
40 Correct 30 ms 47692 KB Output is correct
41 Correct 30 ms 47816 KB Output is correct
42 Correct 32 ms 47848 KB Output is correct
43 Correct 30 ms 47788 KB Output is correct
44 Correct 30 ms 47860 KB Output is correct
45 Correct 29 ms 47360 KB Output is correct
46 Correct 487 ms 93188 KB Output is correct
47 Correct 513 ms 103640 KB Output is correct
48 Correct 491 ms 91788 KB Output is correct
49 Correct 541 ms 93344 KB Output is correct
50 Correct 533 ms 91968 KB Output is correct
51 Correct 526 ms 93144 KB Output is correct
52 Correct 565 ms 92104 KB Output is correct
53 Correct 472 ms 93148 KB Output is correct
54 Correct 590 ms 94800 KB Output is correct
55 Correct 547 ms 93100 KB Output is correct
56 Correct 473 ms 92424 KB Output is correct
57 Correct 431 ms 93528 KB Output is correct
58 Correct 570 ms 100916 KB Output is correct
59 Correct 385 ms 94356 KB Output is correct
60 Correct 35 ms 47276 KB Output is correct
61 Correct 594 ms 95756 KB Output is correct
62 Correct 558 ms 105456 KB Output is correct
63 Correct 559 ms 94492 KB Output is correct
64 Correct 555 ms 95836 KB Output is correct
65 Correct 570 ms 94484 KB Output is correct
66 Correct 574 ms 95788 KB Output is correct
67 Correct 533 ms 94540 KB Output is correct
68 Correct 538 ms 95956 KB Output is correct
69 Correct 598 ms 97500 KB Output is correct
70 Correct 620 ms 95448 KB Output is correct
71 Correct 508 ms 95160 KB Output is correct
72 Correct 491 ms 96656 KB Output is correct
73 Correct 619 ms 103152 KB Output is correct
74 Correct 466 ms 98512 KB Output is correct