oj.uz

Submission #893782

# Submission time Handle Problem Language Result Execution time Memory
893782 2023-12-27T12:14:28 Z lolismek Tourism (JOI23_tourism) C++14
100 / 100
 1134 ms 22132 KB 
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <random>
#include <chrono>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ull = unsigned long long;
using ll = long long;

//#define int __int128
//#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound

#define vt vector
#define FOR(a, b) for(int i = (a); ((a) <= (b) ? i <= (b) : i >= (b));((a) <= (b) ? i++ : i--))
#define sz(x) (int)(x).size() // ?

#define YES fout << "YES\n"
#define NO fout << "NO\n"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rangerng(int l, int r){
    return uniform_int_distribution<>(l, r)(rng);
}

////////////////////////////////////////////////////////////////////////////////////

// ifstream fin("input.in");
// ofstream fout("output.out");

#define fin cin
#define fout cout

const int NMAX = 1e5 + 5; // ?

vt <int> adj[NMAX + 1];
int c[NMAX + 1];
vt <pii> quer[NMAX + 1];

int Ans[NMAX + 1];

int sz[NMAX + 1];
int par[NMAX + 1];
int hvChild[NMAX + 1];

int lvl[NMAX + 1];

void expl(int node, int parent){
    par[node] = parent;
    sz[node] = 1;

    lvl[node] = lvl[parent] + 1;

    int maxi = 0;
    for(int child : adj[node]){
        if(child != parent){
            expl(child, node);
            sz[node] += sz[child];

            if(sz[child] > maxi){
                maxi = sz[child];
                hvChild[node] = child;
            }
        }
    }
}

int Id = 0;
int id[NMAX + 1];
int head[NMAX + 1];
int last[NMAX + 1];

int Time = 0;
int pos[NMAX + 1];

void hvFirst(int node, int parent){
    pos[node] = ++Time;
    
    if(hvChild[parent] != node){
        id[node] = ++Id;
        head[Id] = node;
    }else{
        id[node] = id[parent];
    }

    last[id[node]] = node;

    if(hvChild[node] != 0){
        hvFirst(hvChild[node], node);
    }

    for(int child : adj[node]){
        if(child != parent && child != hvChild[node]){
            hvFirst(child, node);
        }
    }
}

namespace AIB{
    int n;
    int aib[NMAX + 2];

    void init(int _n){
        n = _n + 1;
        FOR(1, n){
            aib[i] = 0;
        }
    }

    int lsb(int x){
        return x & -x;
    }

    void update(int pos, int val){
        pos++;
        for(int i = pos; i <= n; i += lsb(i)){
            aib[i] += val;
        }
    }

    int query(int pos){
        int ans = 0;
        pos++;
        for(int i = pos; i >= 1; i -= lsb(i)){
            ans += aib[i];
        }
        return ans;
    }
}

set <pair <pii, int>> S;

void setInterval(int l, int r, int x){
    vt <pair <pii, int>> toErase;
    vt <pair <pii, int>> toInsert;
    toInsert.pb({{l, r}, x});

    for(auto it = S.lb({{l, 0}, 0}); it != S.end() && (*it).fr.fr <= r; it++){
        pair <pii, int> obj = (*it);
        toErase.pb(obj);
        if(obj.fr.sc > r){
            pair <pii, int> newObj = {{r + 1, obj.fr.sc}, obj.sc};
            toInsert.pb(newObj);
        }
    }

    auto it = S.lb({{l, 0}, 0});
    if(it != S.begin()){
        it--;
        pair <pii, int> obj = (*it);
        if(obj.fr.fr < l && obj.fr.sc >= l){
            toErase.pb(obj);
            toInsert.pb({{obj.fr.fr, l - 1}, obj.sc});
            if(obj.fr.sc > r){
                toInsert.pb({{r + 1, obj.fr.sc}, obj.sc});
            }
        }
    }

    for(auto x : toErase){
        S.erase(x);
        AIB::update(x.sc, -(x.fr.sc - x.fr.fr + 1));
    }

    for(auto x : toInsert){
        S.insert(x);
        AIB::update(x.sc, +(x.fr.sc - x.fr.fr + 1));
    }
}

void update(int a, int b, int x){
    while(id[a] != id[b]){
        if(lvl[head[id[a]]] > lvl[head[id[b]]]){
            setInterval(pos[head[id[a]]], pos[a], x);
            a = par[head[id[a]]];
        }else{
            setInterval(pos[head[id[b]]], pos[b], x);
            b = par[head[id[b]]];
        }
    }
    setInterval(min(pos[a], pos[b]), max(pos[a], pos[b]), x);
}

void solve(){
    int n, m, q;
    fin >> n >> m >> q;

    for(int i = 1; i <= n - 1; i++){
        int a, b;
        fin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    FOR(1, m){
        fin >> c[i];
    }

    FOR(1, q){
        int x, y;
        fin >> x >> y;
        quer[y].pb({x, i});
    }

    expl(1, 0);
    hvFirst(1, 0);

    AIB::init(m);

    FOR(1, Id){
        S.insert({{pos[head[i]], pos[last[i]]}, 0});
        AIB::update(0, pos[last[i]] - pos[head[i]] + 1);
    }

    FOR(1, m){
        if(i > 1){
            update(c[i - 1], c[i], i - 1);
        }
        update(c[i], c[i], i);

        for(pii x : quer[i]){
            Ans[x.sc] += AIB::query(m) - AIB::query(x.fr - 1);
        }
    }

    for(int i = 1; i <= q; i++){
        fout << Ans[i] << '\n';
    }
}       

signed main(){

    ios_base::sync_with_stdio(false);
    fin.tie(0);

    int T;
    //fin >> T;

    T = 1;

    while(T--){
        solve();
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7260 KB Output is correct
21 Correct 2 ms 7260 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7256 KB Output is correct
24 Correct 2 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 2 ms 7260 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7260 KB Output is correct
21 Correct 2 ms 7260 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7256 KB Output is correct
24 Correct 2 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 2 ms 7260 KB Output is correct
30 Correct 7 ms 7260 KB Output is correct
31 Correct 7 ms 7436 KB Output is correct
32 Correct 9 ms 7260 KB Output is correct
33 Correct 9 ms 7504 KB Output is correct
34 Correct 9 ms 7516 KB Output is correct
35 Correct 8 ms 7260 KB Output is correct
36 Correct 9 ms 7516 KB Output is correct
37 Correct 9 ms 7260 KB Output is correct
38 Correct 4 ms 7260 KB Output is correct
39 Correct 5 ms 7516 KB Output is correct
40 Correct 5 ms 7516 KB Output is correct
41 Correct 4 ms 7516 KB Output is correct
42 Correct 4 ms 7516 KB Output is correct
43 Correct 4 ms 7260 KB Output is correct
44 Correct 6 ms 7260 KB Output is correct
45 Correct 6 ms 7260 KB Output is correct
46 Correct 6 ms 7260 KB Output is correct
47 Correct 6 ms 7256 KB Output is correct
48 Correct 6 ms 7260 KB Output is correct
49 Correct 6 ms 7260 KB Output is correct
50 Correct 8 ms 7516 KB Output is correct
51 Correct 6 ms 7516 KB Output is correct
52 Correct 5 ms 7544 KB Output is correct
53 Correct 5 ms 7516 KB Output is correct
54 Correct 5 ms 7516 KB Output is correct
55 Correct 5 ms 7512 KB Output is correct
56 Correct 2 ms 7260 KB Output is correct
57 Correct 2 ms 7260 KB Output is correct
58 Correct 8 ms 7504 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 122 ms 16140 KB Output is correct
5 Correct 96 ms 18704 KB Output is correct
6 Correct 119 ms 20052 KB Output is correct
7 Correct 155 ms 22128 KB Output is correct
8 Correct 164 ms 22128 KB Output is correct
9 Correct 152 ms 22120 KB Output is correct
10 Correct 151 ms 22096 KB Output is correct
11 Correct 156 ms 22132 KB Output is correct
12 Correct 155 ms 21844 KB Output is correct
13 Correct 156 ms 21724 KB Output is correct
14 Correct 160 ms 21728 KB Output is correct
15 Correct 38 ms 20160 KB Output is correct
16 Correct 147 ms 21844 KB Output is correct
17 Correct 51 ms 9812 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 341 ms 12700 KB Output is correct
3 Correct 535 ms 13044 KB Output is correct
4 Correct 426 ms 13996 KB Output is correct
5 Correct 734 ms 16956 KB Output is correct
6 Correct 677 ms 16680 KB Output is correct
7 Correct 663 ms 16628 KB Output is correct
8 Correct 710 ms 16696 KB Output is correct
9 Correct 670 ms 16664 KB Output is correct
10 Correct 691 ms 16916 KB Output is correct
11 Correct 674 ms 16720 KB Output is correct
12 Correct 688 ms 16724 KB Output is correct
13 Correct 726 ms 17072 KB Output is correct
14 Correct 707 ms 17700 KB Output is correct
15 Correct 750 ms 20020 KB Output is correct
16 Correct 703 ms 17228 KB Output is correct
17 Correct 715 ms 17248 KB Output is correct
18 Correct 655 ms 17116 KB Output is correct
19 Correct 409 ms 12116 KB Output is correct
20 Correct 486 ms 12480 KB Output is correct
21 Correct 430 ms 12124 KB Output is correct
22 Correct 430 ms 12432 KB Output is correct
23 Correct 400 ms 12116 KB Output is correct
24 Correct 426 ms 12168 KB Output is correct
25 Correct 408 ms 12124 KB Output is correct
26 Correct 422 ms 12260 KB Output is correct
27 Correct 406 ms 12420 KB Output is correct
28 Correct 444 ms 12216 KB Output is correct
29 Correct 427 ms 12544 KB Output is correct
30 Correct 469 ms 12400 KB Output is correct
31 Correct 423 ms 12628 KB Output is correct
32 Correct 421 ms 12884 KB Output is correct
33 Correct 452 ms 13948 KB Output is correct
34 Correct 425 ms 15444 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 819 ms 15420 KB Output is correct
5 Correct 885 ms 15552 KB Output is correct
6 Correct 998 ms 18148 KB Output is correct
7 Correct 1121 ms 19536 KB Output is correct
8 Correct 1134 ms 19736 KB Output is correct
9 Correct 1059 ms 19596 KB Output is correct
10 Correct 1075 ms 19660 KB Output is correct
11 Correct 1031 ms 19676 KB Output is correct
12 Correct 1082 ms 19736 KB Output is correct
13 Correct 1081 ms 19812 KB Output is correct
14 Correct 51 ms 9812 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7256 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 7260 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 3 ms 7260 KB Output is correct
17 Correct 2 ms 7260 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7260 KB Output is correct
21 Correct 2 ms 7260 KB Output is correct
22 Correct 2 ms 7260 KB Output is correct
23 Correct 2 ms 7256 KB Output is correct
24 Correct 2 ms 7260 KB Output is correct
25 Correct 2 ms 7260 KB Output is correct
26 Correct 2 ms 7260 KB Output is correct
27 Correct 2 ms 7260 KB Output is correct
28 Correct 2 ms 7260 KB Output is correct
29 Correct 2 ms 7260 KB Output is correct
30 Correct 7 ms 7260 KB Output is correct
31 Correct 7 ms 7436 KB Output is correct
32 Correct 9 ms 7260 KB Output is correct
33 Correct 9 ms 7504 KB Output is correct
34 Correct 9 ms 7516 KB Output is correct
35 Correct 8 ms 7260 KB Output is correct
36 Correct 9 ms 7516 KB Output is correct
37 Correct 9 ms 7260 KB Output is correct
38 Correct 4 ms 7260 KB Output is correct
39 Correct 5 ms 7516 KB Output is correct
40 Correct 5 ms 7516 KB Output is correct
41 Correct 4 ms 7516 KB Output is correct
42 Correct 4 ms 7516 KB Output is correct
43 Correct 4 ms 7260 KB Output is correct
44 Correct 6 ms 7260 KB Output is correct
45 Correct 6 ms 7260 KB Output is correct
46 Correct 6 ms 7260 KB Output is correct
47 Correct 6 ms 7256 KB Output is correct
48 Correct 6 ms 7260 KB Output is correct
49 Correct 6 ms 7260 KB Output is correct
50 Correct 8 ms 7516 KB Output is correct
51 Correct 6 ms 7516 KB Output is correct
52 Correct 5 ms 7544 KB Output is correct
53 Correct 5 ms 7516 KB Output is correct
54 Correct 5 ms 7516 KB Output is correct
55 Correct 5 ms 7512 KB Output is correct
56 Correct 2 ms 7260 KB Output is correct
57 Correct 2 ms 7260 KB Output is correct
58 Correct 8 ms 7504 KB Output is correct
59 Correct 2 ms 7260 KB Output is correct
60 Correct 2 ms 7260 KB Output is correct
61 Correct 2 ms 7260 KB Output is correct
62 Correct 122 ms 16140 KB Output is correct
63 Correct 96 ms 18704 KB Output is correct
64 Correct 119 ms 20052 KB Output is correct
65 Correct 155 ms 22128 KB Output is correct
66 Correct 164 ms 22128 KB Output is correct
67 Correct 152 ms 22120 KB Output is correct
68 Correct 151 ms 22096 KB Output is correct
69 Correct 156 ms 22132 KB Output is correct
70 Correct 155 ms 21844 KB Output is correct
71 Correct 156 ms 21724 KB Output is correct
72 Correct 160 ms 21728 KB Output is correct
73 Correct 38 ms 20160 KB Output is correct
74 Correct 147 ms 21844 KB Output is correct
75 Correct 51 ms 9812 KB Output is correct
76 Correct 1 ms 7260 KB Output is correct
77 Correct 341 ms 12700 KB Output is correct
78 Correct 535 ms 13044 KB Output is correct
79 Correct 426 ms 13996 KB Output is correct
80 Correct 734 ms 16956 KB Output is correct
81 Correct 677 ms 16680 KB Output is correct
82 Correct 663 ms 16628 KB Output is correct
83 Correct 710 ms 16696 KB Output is correct
84 Correct 670 ms 16664 KB Output is correct
85 Correct 691 ms 16916 KB Output is correct
86 Correct 674 ms 16720 KB Output is correct
87 Correct 688 ms 16724 KB Output is correct
88 Correct 726 ms 17072 KB Output is correct
89 Correct 707 ms 17700 KB Output is correct
90 Correct 750 ms 20020 KB Output is correct
91 Correct 703 ms 17228 KB Output is correct
92 Correct 715 ms 17248 KB Output is correct
93 Correct 655 ms 17116 KB Output is correct
94 Correct 409 ms 12116 KB Output is correct
95 Correct 486 ms 12480 KB Output is correct
96 Correct 430 ms 12124 KB Output is correct
97 Correct 430 ms 12432 KB Output is correct
98 Correct 400 ms 12116 KB Output is correct
99 Correct 426 ms 12168 KB Output is correct
100 Correct 408 ms 12124 KB Output is correct
101 Correct 422 ms 12260 KB Output is correct
102 Correct 406 ms 12420 KB Output is correct
103 Correct 444 ms 12216 KB Output is correct
104 Correct 427 ms 12544 KB Output is correct
105 Correct 469 ms 12400 KB Output is correct
106 Correct 423 ms 12628 KB Output is correct
107 Correct 421 ms 12884 KB Output is correct
108 Correct 452 ms 13948 KB Output is correct
109 Correct 425 ms 15444 KB Output is correct
110 Correct 2 ms 7256 KB Output is correct
111 Correct 2 ms 7260 KB Output is correct
112 Correct 2 ms 7260 KB Output is correct
113 Correct 819 ms 15420 KB Output is correct
114 Correct 885 ms 15552 KB Output is correct
115 Correct 998 ms 18148 KB Output is correct
116 Correct 1121 ms 19536 KB Output is correct
117 Correct 1134 ms 19736 KB Output is correct
118 Correct 1059 ms 19596 KB Output is correct
119 Correct 1075 ms 19660 KB Output is correct
120 Correct 1031 ms 19676 KB Output is correct
121 Correct 1082 ms 19736 KB Output is correct
122 Correct 1081 ms 19812 KB Output is correct
123 Correct 51 ms 9812 KB Output is correct
124 Correct 609 ms 19188 KB Output is correct
125 Correct 455 ms 17584 KB Output is correct
126 Correct 764 ms 19320 KB Output is correct
127 Correct 850 ms 19300 KB Output is correct
128 Correct 715 ms 19360 KB Output is correct
129 Correct 800 ms 19176 KB Output is correct
130 Correct 718 ms 19296 KB Output is correct
131 Correct 162 ms 20944 KB Output is correct
132 Correct 168 ms 22016 KB Output is correct
133 Correct 165 ms 18228 KB Output is correct
134 Correct 431 ms 14768 KB Output is correct
135 Correct 459 ms 14748 KB Output is correct
136 Correct 467 ms 14964 KB Output is correct
137 Correct 285 ms 21736 KB Output is correct
138 Correct 307 ms 21964 KB Output is correct
139 Correct 287 ms 21728 KB Output is correct
140 Correct 280 ms 21708 KB Output is correct
141 Correct 310 ms 21696 KB Output is correct
142 Correct 301 ms 21760 KB Output is correct
143 Correct 48 ms 15816 KB Output is correct
144 Correct 736 ms 19044 KB Output is correct