oj.uz

Submission #926070

# Submission time Handle Problem Language Result Execution time Memory
926070 2024-02-12T14:20:21 Z ttamx Tourism (JOI23_tourism) C++14
100 / 100
 191 ms 101124 KB 
#include<bits/stdc++.h>
#include<queue>

using namespace std;

const int N=1e5+5;
const int M=3e5+5;
const int LG=20;

int n,m,q;
int c[N];
vector<int> adj[N];
int sz[N],hv[N],hd[N],pa[N],lv[N],tin[N],tout[N],pos[M];
int timer;
vector<pair<int,int>> qr[N],chain[N];
int ans[N];

struct Fenwick{
    int t[N];
    void update(int i,int v){
        for(;i<N;i+=i&-i)t[i]+=v;
    }
    int query(int i){
        int res=0;
        for(;i;i-=i&-i)res+=t[i];
        return res;
    }
}f;

template<class T,class cmp>
struct RMQ{
    T t[LG][M];
    T get_min(T a,T b){
        return cmp()(a,b)?a:b;
    }
    void build(){
        for(int i=0;i<LG-1;i++){
            for(int j=1;j+(2<<i)-1<M;j++){
                t[i+1][j]=get_min(t[i][j],t[i][j+(1<<i)]);
            }
        }
    }
    T query(int l,int r){
        int k=31-__builtin_clz(r-l+1);
        return get_min(t[k][l],t[k][r-(1<<k)+1]);
    }
};

RMQ<int,less<int>> rtin,rdep;
RMQ<int,greater<int>> rtout;

void dfs(int u,int p=0){
    tin[u]=++timer;
    pos[timer]=u;
    pa[u]=p;
    sz[u]=1;
    for(auto v:adj[u])if(v!=p){
        lv[v]=lv[u]+1;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[hv[u]])hv[u]=v;
        pos[++timer]=u;
    }
    tout[u]=timer;
}

void hld(int u,int p=0){
    if(!hd[u])hd[u]=u;
    if(hv[u])hd[hv[u]]=hd[u],hld(hv[u],u);
    for(auto v:adj[u])if(v!=p&&v!=hv[u])hld(v,u);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    for(int i=1;i<=m;i++)cin >> c[i];
    for(int i=1;i<=q;i++){
        int l,r;
        cin >> l >> r;
        qr[r].emplace_back(l,i);
    }
    dfs(1);
    hld(1);
    for(int i=1;i<=timer;i++)rdep.t[0][i]=lv[pos[i]];
    for(int i=1;i<=m;i++){
        rtin.t[0][i]=tin[c[i]];
        rtout.t[0][i]=tout[c[i]];
    }
    rdep.build();
    rtin.build();
    rtout.build();
    for(int r=1;r<=m;r++){
        for(int u=c[r];u;u=pa[hd[u]]){
            int h=hd[u];
            auto &ch=chain[h];
            while(!ch.empty()&&lv[ch.back().first]<=lv[u]){
                auto [v,i]=ch.back();
                ch.pop_back();
                int val=lv[v]-lv[h]+1;
                f.update(i,-val);
                if(!ch.empty())f.update(ch.back().second,val);
            }
            int val=lv[u]-lv[h]+1;
            if(!ch.empty())f.update(ch.back().second,-val);
            ch.emplace_back(u,r);
            f.update(r,lv[u]-lv[h]+1);
        }
        for(auto [l,i]:qr[r]){
            int u=rtin.query(l,r),v=rtout.query(l,r);
            ans[i]=f.query(r)-f.query(l-1)-rdep.query(u,v);
        }
    }
    for(int i=1;i<=q;i++)cout << ans[i] << "\n";
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:103:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |                 auto [v,i]=ch.back();
      |                      ^
tourism.cpp:114:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |         for(auto [l,i]:qr[r]){
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 82516 KB Output is correct
2 Correct 23 ms 82524 KB Output is correct
3 Correct 24 ms 82400 KB Output is correct
4 Correct 25 ms 82524 KB Output is correct
5 Correct 22 ms 82460 KB Output is correct
6 Correct 22 ms 82512 KB Output is correct
7 Correct 22 ms 82524 KB Output is correct
8 Correct 22 ms 82440 KB Output is correct
9 Correct 22 ms 82396 KB Output is correct
10 Correct 22 ms 82520 KB Output is correct
11 Correct 22 ms 82512 KB Output is correct
12 Correct 21 ms 82524 KB Output is correct
13 Correct 22 ms 82520 KB Output is correct
14 Correct 22 ms 82512 KB Output is correct
15 Correct 22 ms 82524 KB Output is correct
16 Correct 22 ms 82524 KB Output is correct
17 Correct 22 ms 82512 KB Output is correct
18 Correct 22 ms 82524 KB Output is correct
19 Correct 22 ms 82524 KB Output is correct
20 Correct 23 ms 82500 KB Output is correct
21 Correct 22 ms 82524 KB Output is correct
22 Correct 23 ms 82780 KB Output is correct
23 Correct 22 ms 82580 KB Output is correct
24 Correct 22 ms 82524 KB Output is correct
25 Correct 22 ms 82524 KB Output is correct
26 Correct 22 ms 82512 KB Output is correct
27 Correct 22 ms 82520 KB Output is correct
28 Correct 22 ms 82516 KB Output is correct
29 Correct 23 ms 82524 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 82516 KB Output is correct
2 Correct 23 ms 82524 KB Output is correct
3 Correct 24 ms 82400 KB Output is correct
4 Correct 25 ms 82524 KB Output is correct
5 Correct 22 ms 82460 KB Output is correct
6 Correct 22 ms 82512 KB Output is correct
7 Correct 22 ms 82524 KB Output is correct
8 Correct 22 ms 82440 KB Output is correct
9 Correct 22 ms 82396 KB Output is correct
10 Correct 22 ms 82520 KB Output is correct
11 Correct 22 ms 82512 KB Output is correct
12 Correct 21 ms 82524 KB Output is correct
13 Correct 22 ms 82520 KB Output is correct
14 Correct 22 ms 82512 KB Output is correct
15 Correct 22 ms 82524 KB Output is correct
16 Correct 22 ms 82524 KB Output is correct
17 Correct 22 ms 82512 KB Output is correct
18 Correct 22 ms 82524 KB Output is correct
19 Correct 22 ms 82524 KB Output is correct
20 Correct 23 ms 82500 KB Output is correct
21 Correct 22 ms 82524 KB Output is correct
22 Correct 23 ms 82780 KB Output is correct
23 Correct 22 ms 82580 KB Output is correct
24 Correct 22 ms 82524 KB Output is correct
25 Correct 22 ms 82524 KB Output is correct
26 Correct 22 ms 82512 KB Output is correct
27 Correct 22 ms 82520 KB Output is correct
28 Correct 22 ms 82516 KB Output is correct
29 Correct 23 ms 82524 KB Output is correct
30 Correct 23 ms 82516 KB Output is correct
31 Correct 23 ms 82516 KB Output is correct
32 Correct 26 ms 82616 KB Output is correct
33 Correct 24 ms 82512 KB Output is correct
34 Correct 23 ms 82728 KB Output is correct
35 Correct 24 ms 82512 KB Output is correct
36 Correct 25 ms 82516 KB Output is correct
37 Correct 23 ms 82520 KB Output is correct
38 Correct 23 ms 82748 KB Output is correct
39 Correct 24 ms 82728 KB Output is correct
40 Correct 23 ms 82780 KB Output is correct
41 Correct 23 ms 82780 KB Output is correct
42 Correct 23 ms 82780 KB Output is correct
43 Correct 23 ms 82672 KB Output is correct
44 Correct 23 ms 82776 KB Output is correct
45 Correct 23 ms 82680 KB Output is correct
46 Correct 25 ms 82516 KB Output is correct
47 Correct 23 ms 82524 KB Output is correct
48 Correct 23 ms 82516 KB Output is correct
49 Correct 23 ms 82524 KB Output is correct
50 Correct 23 ms 82696 KB Output is correct
51 Correct 23 ms 82524 KB Output is correct
52 Correct 23 ms 82520 KB Output is correct
53 Correct 23 ms 82524 KB Output is correct
54 Correct 23 ms 82596 KB Output is correct
55 Correct 24 ms 82524 KB Output is correct
56 Correct 23 ms 82512 KB Output is correct
57 Correct 24 ms 82516 KB Output is correct
58 Correct 24 ms 82620 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 82452 KB Output is correct
2 Correct 22 ms 82520 KB Output is correct
3 Correct 23 ms 82524 KB Output is correct
4 Correct 77 ms 93776 KB Output is correct
5 Correct 71 ms 96460 KB Output is correct
6 Correct 73 ms 98096 KB Output is correct
7 Correct 98 ms 101124 KB Output is correct
8 Correct 96 ms 100904 KB Output is correct
9 Correct 90 ms 100824 KB Output is correct
10 Correct 93 ms 100892 KB Output is correct
11 Correct 94 ms 100936 KB Output is correct
12 Correct 79 ms 99920 KB Output is correct
13 Correct 76 ms 99924 KB Output is correct
14 Correct 76 ms 99924 KB Output is correct
15 Correct 66 ms 97680 KB Output is correct
16 Correct 93 ms 100540 KB Output is correct
17 Correct 58 ms 86536 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 82524 KB Output is correct
2 Correct 66 ms 86112 KB Output is correct
3 Correct 87 ms 87128 KB Output is correct
4 Correct 80 ms 87204 KB Output is correct
5 Correct 103 ms 89168 KB Output is correct
6 Correct 108 ms 89168 KB Output is correct
7 Correct 104 ms 89224 KB Output is correct
8 Correct 117 ms 89112 KB Output is correct
9 Correct 107 ms 89136 KB Output is correct
10 Correct 103 ms 89252 KB Output is correct
11 Correct 103 ms 89172 KB Output is correct
12 Correct 105 ms 89284 KB Output is correct
13 Correct 106 ms 89684 KB Output is correct
14 Correct 113 ms 90648 KB Output is correct
15 Correct 140 ms 93728 KB Output is correct
16 Correct 113 ms 89680 KB Output is correct
17 Correct 118 ms 89684 KB Output is correct
18 Correct 105 ms 89708 KB Output is correct
19 Correct 82 ms 87976 KB Output is correct
20 Correct 81 ms 88124 KB Output is correct
21 Correct 83 ms 87888 KB Output is correct
22 Correct 84 ms 88164 KB Output is correct
23 Correct 84 ms 88144 KB Output is correct
24 Correct 81 ms 88116 KB Output is correct
25 Correct 85 ms 87956 KB Output is correct
26 Correct 87 ms 88172 KB Output is correct
27 Correct 84 ms 88144 KB Output is correct
28 Correct 89 ms 87920 KB Output is correct
29 Correct 84 ms 88148 KB Output is correct
30 Correct 87 ms 88400 KB Output is correct
31 Correct 88 ms 88400 KB Output is correct
32 Correct 89 ms 89108 KB Output is correct
33 Correct 99 ms 90192 KB Output is correct
34 Correct 105 ms 92500 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82516 KB Output is correct
2 Correct 22 ms 82404 KB Output is correct
3 Correct 22 ms 82584 KB Output is correct
4 Correct 133 ms 90192 KB Output is correct
5 Correct 128 ms 90196 KB Output is correct
6 Correct 145 ms 91988 KB Output is correct
7 Correct 191 ms 92992 KB Output is correct
8 Correct 152 ms 93008 KB Output is correct
9 Correct 157 ms 93008 KB Output is correct
10 Correct 155 ms 93012 KB Output is correct
11 Correct 148 ms 92808 KB Output is correct
12 Correct 151 ms 93008 KB Output is correct
13 Correct 171 ms 92956 KB Output is correct
14 Correct 57 ms 86352 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 82516 KB Output is correct
2 Correct 23 ms 82524 KB Output is correct
3 Correct 24 ms 82400 KB Output is correct
4 Correct 25 ms 82524 KB Output is correct
5 Correct 22 ms 82460 KB Output is correct
6 Correct 22 ms 82512 KB Output is correct
7 Correct 22 ms 82524 KB Output is correct
8 Correct 22 ms 82440 KB Output is correct
9 Correct 22 ms 82396 KB Output is correct
10 Correct 22 ms 82520 KB Output is correct
11 Correct 22 ms 82512 KB Output is correct
12 Correct 21 ms 82524 KB Output is correct
13 Correct 22 ms 82520 KB Output is correct
14 Correct 22 ms 82512 KB Output is correct
15 Correct 22 ms 82524 KB Output is correct
16 Correct 22 ms 82524 KB Output is correct
17 Correct 22 ms 82512 KB Output is correct
18 Correct 22 ms 82524 KB Output is correct
19 Correct 22 ms 82524 KB Output is correct
20 Correct 23 ms 82500 KB Output is correct
21 Correct 22 ms 82524 KB Output is correct
22 Correct 23 ms 82780 KB Output is correct
23 Correct 22 ms 82580 KB Output is correct
24 Correct 22 ms 82524 KB Output is correct
25 Correct 22 ms 82524 KB Output is correct
26 Correct 22 ms 82512 KB Output is correct
27 Correct 22 ms 82520 KB Output is correct
28 Correct 22 ms 82516 KB Output is correct
29 Correct 23 ms 82524 KB Output is correct
30 Correct 23 ms 82516 KB Output is correct
31 Correct 23 ms 82516 KB Output is correct
32 Correct 26 ms 82616 KB Output is correct
33 Correct 24 ms 82512 KB Output is correct
34 Correct 23 ms 82728 KB Output is correct
35 Correct 24 ms 82512 KB Output is correct
36 Correct 25 ms 82516 KB Output is correct
37 Correct 23 ms 82520 KB Output is correct
38 Correct 23 ms 82748 KB Output is correct
39 Correct 24 ms 82728 KB Output is correct
40 Correct 23 ms 82780 KB Output is correct
41 Correct 23 ms 82780 KB Output is correct
42 Correct 23 ms 82780 KB Output is correct
43 Correct 23 ms 82672 KB Output is correct
44 Correct 23 ms 82776 KB Output is correct
45 Correct 23 ms 82680 KB Output is correct
46 Correct 25 ms 82516 KB Output is correct
47 Correct 23 ms 82524 KB Output is correct
48 Correct 23 ms 82516 KB Output is correct
49 Correct 23 ms 82524 KB Output is correct
50 Correct 23 ms 82696 KB Output is correct
51 Correct 23 ms 82524 KB Output is correct
52 Correct 23 ms 82520 KB Output is correct
53 Correct 23 ms 82524 KB Output is correct
54 Correct 23 ms 82596 KB Output is correct
55 Correct 24 ms 82524 KB Output is correct
56 Correct 23 ms 82512 KB Output is correct
57 Correct 24 ms 82516 KB Output is correct
58 Correct 24 ms 82620 KB Output is correct
59 Correct 23 ms 82452 KB Output is correct
60 Correct 22 ms 82520 KB Output is correct
61 Correct 23 ms 82524 KB Output is correct
62 Correct 77 ms 93776 KB Output is correct
63 Correct 71 ms 96460 KB Output is correct
64 Correct 73 ms 98096 KB Output is correct
65 Correct 98 ms 101124 KB Output is correct
66 Correct 96 ms 100904 KB Output is correct
67 Correct 90 ms 100824 KB Output is correct
68 Correct 93 ms 100892 KB Output is correct
69 Correct 94 ms 100936 KB Output is correct
70 Correct 79 ms 99920 KB Output is correct
71 Correct 76 ms 99924 KB Output is correct
72 Correct 76 ms 99924 KB Output is correct
73 Correct 66 ms 97680 KB Output is correct
74 Correct 93 ms 100540 KB Output is correct
75 Correct 58 ms 86536 KB Output is correct
76 Correct 23 ms 82524 KB Output is correct
77 Correct 66 ms 86112 KB Output is correct
78 Correct 87 ms 87128 KB Output is correct
79 Correct 80 ms 87204 KB Output is correct
80 Correct 103 ms 89168 KB Output is correct
81 Correct 108 ms 89168 KB Output is correct
82 Correct 104 ms 89224 KB Output is correct
83 Correct 117 ms 89112 KB Output is correct
84 Correct 107 ms 89136 KB Output is correct
85 Correct 103 ms 89252 KB Output is correct
86 Correct 103 ms 89172 KB Output is correct
87 Correct 105 ms 89284 KB Output is correct
88 Correct 106 ms 89684 KB Output is correct
89 Correct 113 ms 90648 KB Output is correct
90 Correct 140 ms 93728 KB Output is correct
91 Correct 113 ms 89680 KB Output is correct
92 Correct 118 ms 89684 KB Output is correct
93 Correct 105 ms 89708 KB Output is correct
94 Correct 82 ms 87976 KB Output is correct
95 Correct 81 ms 88124 KB Output is correct
96 Correct 83 ms 87888 KB Output is correct
97 Correct 84 ms 88164 KB Output is correct
98 Correct 84 ms 88144 KB Output is correct
99 Correct 81 ms 88116 KB Output is correct
100 Correct 85 ms 87956 KB Output is correct
101 Correct 87 ms 88172 KB Output is correct
102 Correct 84 ms 88144 KB Output is correct
103 Correct 89 ms 87920 KB Output is correct
104 Correct 84 ms 88148 KB Output is correct
105 Correct 87 ms 88400 KB Output is correct
106 Correct 88 ms 88400 KB Output is correct
107 Correct 89 ms 89108 KB Output is correct
108 Correct 99 ms 90192 KB Output is correct
109 Correct 105 ms 92500 KB Output is correct
110 Correct 22 ms 82516 KB Output is correct
111 Correct 22 ms 82404 KB Output is correct
112 Correct 22 ms 82584 KB Output is correct
113 Correct 133 ms 90192 KB Output is correct
114 Correct 128 ms 90196 KB Output is correct
115 Correct 145 ms 91988 KB Output is correct
116 Correct 191 ms 92992 KB Output is correct
117 Correct 152 ms 93008 KB Output is correct
118 Correct 157 ms 93008 KB Output is correct
119 Correct 155 ms 93012 KB Output is correct
120 Correct 148 ms 92808 KB Output is correct
121 Correct 151 ms 93008 KB Output is correct
122 Correct 171 ms 92956 KB Output is correct
123 Correct 57 ms 86352 KB Output is correct
124 Correct 136 ms 92496 KB Output is correct
125 Correct 136 ms 90480 KB Output is correct
126 Correct 169 ms 92800 KB Output is correct
127 Correct 141 ms 93012 KB Output is correct
128 Correct 153 ms 93032 KB Output is correct
129 Correct 189 ms 92808 KB Output is correct
130 Correct 175 ms 93040 KB Output is correct
131 Correct 101 ms 99408 KB Output is correct
132 Correct 101 ms 100748 KB Output is correct
133 Correct 132 ms 96084 KB Output is correct
134 Correct 135 ms 91732 KB Output is correct
135 Correct 129 ms 91988 KB Output is correct
136 Correct 123 ms 91676 KB Output is correct
137 Correct 115 ms 93904 KB Output is correct
138 Correct 129 ms 93940 KB Output is correct
139 Correct 107 ms 93952 KB Output is correct
140 Correct 109 ms 93820 KB Output is correct
141 Correct 135 ms 93928 KB Output is correct
142 Correct 106 ms 93820 KB Output is correct
143 Correct 88 ms 88232 KB Output is correct
144 Correct 172 ms 92756 KB Output is correct