oj.uz

Submission #924667

# Submission time Handle Problem Language Result Execution time Memory
924667 2024-02-09T11:50:32 Z ttamx Tourism (JOI23_tourism) C++14
100 / 100
 170 ms 101228 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++){
        int cnt=0;
        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,val);
        }
        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:104:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |                 auto [v,i]=ch.back();
      |                      ^
tourism.cpp:115:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |         for(auto [l,i]:qr[r]){
      |                  ^
tourism.cpp:99:13: warning: unused variable 'cnt' [-Wunused-variable]
   99 |         int cnt=0;
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82264 KB Output is correct
2 Correct 21 ms 82524 KB Output is correct
3 Correct 22 ms 82520 KB Output is correct
4 Correct 23 ms 82552 KB Output is correct
5 Correct 23 ms 82524 KB Output is correct
6 Correct 22 ms 82524 KB Output is correct
7 Correct 22 ms 82496 KB Output is correct
8 Correct 22 ms 82516 KB Output is correct
9 Correct 22 ms 82524 KB Output is correct
10 Correct 24 ms 82472 KB Output is correct
11 Correct 22 ms 82524 KB Output is correct
12 Correct 22 ms 82524 KB Output is correct
13 Correct 22 ms 82524 KB Output is correct
14 Correct 22 ms 82480 KB Output is correct
15 Correct 24 ms 82524 KB Output is correct
16 Correct 22 ms 82500 KB Output is correct
17 Correct 23 ms 82516 KB Output is correct
18 Correct 22 ms 82520 KB Output is correct
19 Correct 22 ms 82520 KB Output is correct
20 Correct 24 ms 82452 KB Output is correct
21 Correct 22 ms 82524 KB Output is correct
22 Correct 22 ms 82520 KB Output is correct
23 Correct 22 ms 82524 KB Output is correct
24 Correct 22 ms 82512 KB Output is correct
25 Correct 22 ms 82524 KB Output is correct
26 Correct 22 ms 82508 KB Output is correct
27 Correct 23 ms 82456 KB Output is correct
28 Correct 22 ms 82280 KB Output is correct
29 Correct 22 ms 82516 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82264 KB Output is correct
2 Correct 21 ms 82524 KB Output is correct
3 Correct 22 ms 82520 KB Output is correct
4 Correct 23 ms 82552 KB Output is correct
5 Correct 23 ms 82524 KB Output is correct
6 Correct 22 ms 82524 KB Output is correct
7 Correct 22 ms 82496 KB Output is correct
8 Correct 22 ms 82516 KB Output is correct
9 Correct 22 ms 82524 KB Output is correct
10 Correct 24 ms 82472 KB Output is correct
11 Correct 22 ms 82524 KB Output is correct
12 Correct 22 ms 82524 KB Output is correct
13 Correct 22 ms 82524 KB Output is correct
14 Correct 22 ms 82480 KB Output is correct
15 Correct 24 ms 82524 KB Output is correct
16 Correct 22 ms 82500 KB Output is correct
17 Correct 23 ms 82516 KB Output is correct
18 Correct 22 ms 82520 KB Output is correct
19 Correct 22 ms 82520 KB Output is correct
20 Correct 24 ms 82452 KB Output is correct
21 Correct 22 ms 82524 KB Output is correct
22 Correct 22 ms 82520 KB Output is correct
23 Correct 22 ms 82524 KB Output is correct
24 Correct 22 ms 82512 KB Output is correct
25 Correct 22 ms 82524 KB Output is correct
26 Correct 22 ms 82508 KB Output is correct
27 Correct 23 ms 82456 KB Output is correct
28 Correct 22 ms 82280 KB Output is correct
29 Correct 22 ms 82516 KB Output is correct
30 Correct 24 ms 82516 KB Output is correct
31 Correct 23 ms 82524 KB Output is correct
32 Correct 24 ms 82516 KB Output is correct
33 Correct 23 ms 82524 KB Output is correct
34 Correct 25 ms 82512 KB Output is correct
35 Correct 23 ms 82516 KB Output is correct
36 Correct 24 ms 82516 KB Output is correct
37 Correct 24 ms 82524 KB Output is correct
38 Correct 24 ms 82684 KB Output is correct
39 Correct 24 ms 82764 KB Output is correct
40 Correct 23 ms 82768 KB Output is correct
41 Correct 24 ms 82776 KB Output is correct
42 Correct 23 ms 82724 KB Output is correct
43 Correct 23 ms 82688 KB Output is correct
44 Correct 23 ms 82520 KB Output is correct
45 Correct 25 ms 82524 KB Output is correct
46 Correct 23 ms 82516 KB Output is correct
47 Correct 24 ms 82520 KB Output is correct
48 Correct 23 ms 82616 KB Output is correct
49 Correct 23 ms 82524 KB Output is correct
50 Correct 24 ms 82612 KB Output is correct
51 Correct 24 ms 82636 KB Output is correct
52 Correct 24 ms 82636 KB Output is correct
53 Correct 23 ms 82520 KB Output is correct
54 Correct 23 ms 82512 KB Output is correct
55 Correct 24 ms 82624 KB Output is correct
56 Correct 24 ms 82512 KB Output is correct
57 Correct 24 ms 82524 KB Output is correct
58 Correct 24 ms 82524 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82524 KB Output is correct
2 Correct 22 ms 82520 KB Output is correct
3 Correct 22 ms 82528 KB Output is correct
4 Correct 70 ms 91728 KB Output is correct
5 Correct 70 ms 96596 KB Output is correct
6 Correct 80 ms 98076 KB Output is correct
7 Correct 100 ms 100916 KB Output is correct
8 Correct 94 ms 100944 KB Output is correct
9 Correct 94 ms 100852 KB Output is correct
10 Correct 106 ms 101228 KB Output is correct
11 Correct 92 ms 100948 KB Output is correct
12 Correct 77 ms 99924 KB Output is correct
13 Correct 82 ms 99924 KB Output is correct
14 Correct 84 ms 99988 KB Output is correct
15 Correct 61 ms 97544 KB Output is correct
16 Correct 88 ms 100536 KB Output is correct
17 Correct 58 ms 86324 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82524 KB Output is correct
2 Correct 66 ms 85328 KB Output is correct
3 Correct 87 ms 86100 KB Output is correct
4 Correct 77 ms 85988 KB Output is correct
5 Correct 120 ms 87380 KB Output is correct
6 Correct 109 ms 87380 KB Output is correct
7 Correct 115 ms 87456 KB Output is correct
8 Correct 102 ms 87580 KB Output is correct
9 Correct 107 ms 87480 KB Output is correct
10 Correct 105 ms 87404 KB Output is correct
11 Correct 110 ms 87452 KB Output is correct
12 Correct 104 ms 87632 KB Output is correct
13 Correct 109 ms 87788 KB Output is correct
14 Correct 118 ms 88400 KB Output is correct
15 Correct 132 ms 90664 KB Output is correct
16 Correct 107 ms 87956 KB Output is correct
17 Correct 107 ms 87816 KB Output is correct
18 Correct 107 ms 87888 KB Output is correct
19 Correct 84 ms 86356 KB Output is correct
20 Correct 92 ms 86352 KB Output is correct
21 Correct 86 ms 86348 KB Output is correct
22 Correct 85 ms 86352 KB Output is correct
23 Correct 86 ms 86404 KB Output is correct
24 Correct 85 ms 86432 KB Output is correct
25 Correct 85 ms 86352 KB Output is correct
26 Correct 88 ms 86404 KB Output is correct
27 Correct 83 ms 88036 KB Output is correct
28 Correct 86 ms 88112 KB Output is correct
29 Correct 87 ms 88036 KB Output is correct
30 Correct 89 ms 88404 KB Output is correct
31 Correct 87 ms 88440 KB Output is correct
32 Correct 93 ms 88912 KB Output is correct
33 Correct 105 ms 90312 KB Output is correct
34 Correct 116 ms 92640 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 82520 KB Output is correct
2 Correct 22 ms 82520 KB Output is correct
3 Correct 22 ms 82580 KB Output is correct
4 Correct 139 ms 88272 KB Output is correct
5 Correct 131 ms 87888 KB Output is correct
6 Correct 149 ms 89428 KB Output is correct
7 Correct 155 ms 89936 KB Output is correct
8 Correct 157 ms 89936 KB Output is correct
9 Correct 162 ms 90088 KB Output is correct
10 Correct 159 ms 90032 KB Output is correct
11 Correct 170 ms 90044 KB Output is correct
12 Correct 164 ms 89940 KB Output is correct
13 Correct 158 ms 90108 KB Output is correct
14 Correct 60 ms 85072 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 82264 KB Output is correct
2 Correct 21 ms 82524 KB Output is correct
3 Correct 22 ms 82520 KB Output is correct
4 Correct 23 ms 82552 KB Output is correct
5 Correct 23 ms 82524 KB Output is correct
6 Correct 22 ms 82524 KB Output is correct
7 Correct 22 ms 82496 KB Output is correct
8 Correct 22 ms 82516 KB Output is correct
9 Correct 22 ms 82524 KB Output is correct
10 Correct 24 ms 82472 KB Output is correct
11 Correct 22 ms 82524 KB Output is correct
12 Correct 22 ms 82524 KB Output is correct
13 Correct 22 ms 82524 KB Output is correct
14 Correct 22 ms 82480 KB Output is correct
15 Correct 24 ms 82524 KB Output is correct
16 Correct 22 ms 82500 KB Output is correct
17 Correct 23 ms 82516 KB Output is correct
18 Correct 22 ms 82520 KB Output is correct
19 Correct 22 ms 82520 KB Output is correct
20 Correct 24 ms 82452 KB Output is correct
21 Correct 22 ms 82524 KB Output is correct
22 Correct 22 ms 82520 KB Output is correct
23 Correct 22 ms 82524 KB Output is correct
24 Correct 22 ms 82512 KB Output is correct
25 Correct 22 ms 82524 KB Output is correct
26 Correct 22 ms 82508 KB Output is correct
27 Correct 23 ms 82456 KB Output is correct
28 Correct 22 ms 82280 KB Output is correct
29 Correct 22 ms 82516 KB Output is correct
30 Correct 24 ms 82516 KB Output is correct
31 Correct 23 ms 82524 KB Output is correct
32 Correct 24 ms 82516 KB Output is correct
33 Correct 23 ms 82524 KB Output is correct
34 Correct 25 ms 82512 KB Output is correct
35 Correct 23 ms 82516 KB Output is correct
36 Correct 24 ms 82516 KB Output is correct
37 Correct 24 ms 82524 KB Output is correct
38 Correct 24 ms 82684 KB Output is correct
39 Correct 24 ms 82764 KB Output is correct
40 Correct 23 ms 82768 KB Output is correct
41 Correct 24 ms 82776 KB Output is correct
42 Correct 23 ms 82724 KB Output is correct
43 Correct 23 ms 82688 KB Output is correct
44 Correct 23 ms 82520 KB Output is correct
45 Correct 25 ms 82524 KB Output is correct
46 Correct 23 ms 82516 KB Output is correct
47 Correct 24 ms 82520 KB Output is correct
48 Correct 23 ms 82616 KB Output is correct
49 Correct 23 ms 82524 KB Output is correct
50 Correct 24 ms 82612 KB Output is correct
51 Correct 24 ms 82636 KB Output is correct
52 Correct 24 ms 82636 KB Output is correct
53 Correct 23 ms 82520 KB Output is correct
54 Correct 23 ms 82512 KB Output is correct
55 Correct 24 ms 82624 KB Output is correct
56 Correct 24 ms 82512 KB Output is correct
57 Correct 24 ms 82524 KB Output is correct
58 Correct 24 ms 82524 KB Output is correct
59 Correct 21 ms 82524 KB Output is correct
60 Correct 22 ms 82520 KB Output is correct
61 Correct 22 ms 82528 KB Output is correct
62 Correct 70 ms 91728 KB Output is correct
63 Correct 70 ms 96596 KB Output is correct
64 Correct 80 ms 98076 KB Output is correct
65 Correct 100 ms 100916 KB Output is correct
66 Correct 94 ms 100944 KB Output is correct
67 Correct 94 ms 100852 KB Output is correct
68 Correct 106 ms 101228 KB Output is correct
69 Correct 92 ms 100948 KB Output is correct
70 Correct 77 ms 99924 KB Output is correct
71 Correct 82 ms 99924 KB Output is correct
72 Correct 84 ms 99988 KB Output is correct
73 Correct 61 ms 97544 KB Output is correct
74 Correct 88 ms 100536 KB Output is correct
75 Correct 58 ms 86324 KB Output is correct
76 Correct 22 ms 82524 KB Output is correct
77 Correct 66 ms 85328 KB Output is correct
78 Correct 87 ms 86100 KB Output is correct
79 Correct 77 ms 85988 KB Output is correct
80 Correct 120 ms 87380 KB Output is correct
81 Correct 109 ms 87380 KB Output is correct
82 Correct 115 ms 87456 KB Output is correct
83 Correct 102 ms 87580 KB Output is correct
84 Correct 107 ms 87480 KB Output is correct
85 Correct 105 ms 87404 KB Output is correct
86 Correct 110 ms 87452 KB Output is correct
87 Correct 104 ms 87632 KB Output is correct
88 Correct 109 ms 87788 KB Output is correct
89 Correct 118 ms 88400 KB Output is correct
90 Correct 132 ms 90664 KB Output is correct
91 Correct 107 ms 87956 KB Output is correct
92 Correct 107 ms 87816 KB Output is correct
93 Correct 107 ms 87888 KB Output is correct
94 Correct 84 ms 86356 KB Output is correct
95 Correct 92 ms 86352 KB Output is correct
96 Correct 86 ms 86348 KB Output is correct
97 Correct 85 ms 86352 KB Output is correct
98 Correct 86 ms 86404 KB Output is correct
99 Correct 85 ms 86432 KB Output is correct
100 Correct 85 ms 86352 KB Output is correct
101 Correct 88 ms 86404 KB Output is correct
102 Correct 83 ms 88036 KB Output is correct
103 Correct 86 ms 88112 KB Output is correct
104 Correct 87 ms 88036 KB Output is correct
105 Correct 89 ms 88404 KB Output is correct
106 Correct 87 ms 88440 KB Output is correct
107 Correct 93 ms 88912 KB Output is correct
108 Correct 105 ms 90312 KB Output is correct
109 Correct 116 ms 92640 KB Output is correct
110 Correct 21 ms 82520 KB Output is correct
111 Correct 22 ms 82520 KB Output is correct
112 Correct 22 ms 82580 KB Output is correct
113 Correct 139 ms 88272 KB Output is correct
114 Correct 131 ms 87888 KB Output is correct
115 Correct 149 ms 89428 KB Output is correct
116 Correct 155 ms 89936 KB Output is correct
117 Correct 157 ms 89936 KB Output is correct
118 Correct 162 ms 90088 KB Output is correct
119 Correct 159 ms 90032 KB Output is correct
120 Correct 170 ms 90044 KB Output is correct
121 Correct 164 ms 89940 KB Output is correct
122 Correct 158 ms 90108 KB Output is correct
123 Correct 60 ms 85072 KB Output is correct
124 Correct 136 ms 92604 KB Output is correct
125 Correct 114 ms 90640 KB Output is correct
126 Correct 140 ms 93252 KB Output is correct
127 Correct 150 ms 93268 KB Output is correct
128 Correct 145 ms 93076 KB Output is correct
129 Correct 142 ms 92980 KB Output is correct
130 Correct 141 ms 93012 KB Output is correct
131 Correct 105 ms 99436 KB Output is correct
132 Correct 118 ms 100872 KB Output is correct
133 Correct 104 ms 96300 KB Output is correct
134 Correct 118 ms 91740 KB Output is correct
135 Correct 118 ms 91728 KB Output is correct
136 Correct 118 ms 91900 KB Output is correct
137 Correct 101 ms 93892 KB Output is correct
138 Correct 97 ms 93868 KB Output is correct
139 Correct 117 ms 93816 KB Output is correct
140 Correct 102 ms 93740 KB Output is correct
141 Correct 98 ms 93900 KB Output is correct
142 Correct 103 ms 93896 KB Output is correct
143 Correct 64 ms 88376 KB Output is correct
144 Correct 140 ms 92644 KB Output is correct