oj.uz

Submission #793340

# Submission time Handle Problem Language Result Execution time Memory
793340 2023-07-25T18:00:54 Z winter0101 Tourism (JOI23_tourism) C++14
100 / 100
 262 ms 29644 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=1e5+9;
vector<int>a[maxn];
int sub[maxn];
int dep[maxn];
int p[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto &v:a[u]){
    if (v==par)continue;
    dep[v]=dep[u]+1;
    p[v]=u;
    dfs(v,u);
    sub[u]+=sub[v];
    if (a[u][0]==par||sub[a[u][0]]<sub[v])swap(v,a[u][0]);
}
}
int pos[maxn],h[maxn],b[maxn];
int tme=0,gr=1;
void hld(int u,int par,int head){
h[u]=head;
pos[u]=++tme;
b[u]=gr;
if (a[u].empty())return;
if (a[u][0]!=par){
    hld(a[u][0],u,head);
}
for (auto v:a[u]){
    if (v==par||v==a[u][0])continue;
    gr++;
    hld(v,u,v);
}
}
int bit[maxn];
int n,m,q;
void add(int ps,int val){
if (ps==0)return;
for(;ps<=m;ps+=(ps-(ps&(ps-1))))bit[ps]+=val;
}
int get(int ps){
int sum=0;
for(;ps>=1;ps-=(ps-(ps&(ps-1))))sum+=bit[ps];
return sum;
}
int get(int l,int r){
return get(r)-get(l-1);
}
struct tim{
int l,r,w;
bool operator < (const tim &p1)const {
return l<p1.l;
}
};
multiset<tim>line[maxn];
multiset<tim>::iterator it;
void update(int u,int v,int w){
while (h[u]!=h[v]){
    if (dep[h[u]]<dep[h[v]])swap(u,v);
    //cout<<u<<" "<<v<<'\n';
    tim tmp={pos[h[u]],pos[u],w};
    int id=b[u];
    while (!line[id].empty()){
        it=line[id].begin();
        auto temp=(*it);
        if (temp.l>tmp.r)break;
        add(temp.w,-(temp.r-temp.l+1));
        if (temp.r<=tmp.r){
        line[id].erase(it);
        }
        else {
        line[id].erase(it);
        temp.l=tmp.r+1;
        line[id].insert(temp);
        add(temp.w,temp.r-tmp.r);
        }
    }
    add(tmp.w,tmp.r-tmp.l+1);
    line[id].insert(tmp);
    u=p[h[u]];
}
if (pos[u]>pos[v])swap(u,v);
tim tmp={pos[u],pos[v],w};
//cerr<<u<<" "<<v<<'\n';
//cerr<<pos[u]<<" "<<pos[v]<<'\n';
//if (w==5)cerr<<pos[u]<<" "<<pos[v]<<'\n';
int id=b[u];
while (!line[id].empty()){
    it=line[id].upper_bound(tmp);
    if (it==line[id].begin())break;
    //cerr<<"haha"<<'\n';
    it--;
    auto temp=(*it);
    if (temp.r<tmp.l)break;
    add(temp.w,-(temp.r-temp.l+1));
    line[id].erase(it);
    if (temp.r>tmp.r){
    tim t1={tmp.r+1,temp.r,temp.w};
    add(temp.w,temp.r-tmp.r);
    temp.r=tmp.r;
    line[id].insert(t1);
    }
    if (temp.l<tmp.l){
    temp.r=tmp.l-1;
    add(temp.w,temp.r-temp.l+1);
    line[id].insert(temp);
    }
}
while (!line[id].empty()){
    it=line[id].lower_bound(tmp);
    if (it==line[id].end())break;
    auto temp=(*it);
    //cerr<<temp.l<<" "<<temp.r<<'\n';
    if (temp.l>tmp.r)break;
    add(temp.w,-(temp.r-temp.l+1));
    line[id].erase(it);
    if (temp.r<=tmp.r)continue;
    temp.l=tmp.r+1;
    add(temp.w,temp.r-temp.l+1);
    line[id].insert(temp);
}
add(tmp.w,tmp.r-tmp.l+1);
line[id].insert(tmp);
}
int city[maxn];
vector<pii>query[maxn];
int ans[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m>>q;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    dfs(1,0);
    hld(1,0,1);
    for1(i,1,m)cin>>city[i];
    for1(i,1,q){
    int l,r;
    cin>>l>>r;
    if (l==r)ans[i]=1;
    else query[r].pb({l,i});
    }
    for1(i,2,m){
    update(city[i],city[i-1],i-1);
    for (auto v:query[i]){
        ans[v.se]=get(v.fi,i);
    }
    }
    for1(i,1,q)cout<<ans[i]<<'\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 4 ms 9736 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9708 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 5 ms 9736 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 4 ms 9696 KB Output is correct
23 Correct 5 ms 9684 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 5 ms 9684 KB Output is correct
26 Correct 5 ms 9736 KB Output is correct
27 Correct 4 ms 9732 KB Output is correct
28 Correct 4 ms 9684 KB Output is correct
29 Correct 5 ms 9736 KB Output is correct
30 Correct 9 ms 10068 KB Output is correct
31 Correct 7 ms 9892 KB Output is correct
32 Correct 7 ms 10004 KB Output is correct
33 Correct 7 ms 9940 KB Output is correct
34 Correct 7 ms 9940 KB Output is correct
35 Correct 7 ms 9940 KB Output is correct
36 Correct 7 ms 10000 KB Output is correct
37 Correct 6 ms 9940 KB Output is correct
38 Correct 6 ms 10068 KB Output is correct
39 Correct 6 ms 10068 KB Output is correct
40 Correct 6 ms 9992 KB Output is correct
41 Correct 6 ms 10068 KB Output is correct
42 Correct 6 ms 10068 KB Output is correct
43 Correct 6 ms 9940 KB Output is correct
44 Correct 6 ms 9940 KB Output is correct
45 Correct 6 ms 9940 KB Output is correct
46 Correct 7 ms 9936 KB Output is correct
47 Correct 7 ms 9940 KB Output is correct
48 Correct 6 ms 9976 KB Output is correct
49 Correct 9 ms 10068 KB Output is correct
50 Correct 6 ms 9940 KB Output is correct
51 Correct 6 ms 9940 KB Output is correct
52 Correct 6 ms 9940 KB Output is correct
53 Correct 6 ms 9940 KB Output is correct
54 Correct 6 ms 9996 KB Output is correct
55 Correct 6 ms 9940 KB Output is correct
56 Correct 6 ms 9812 KB Output is correct
57 Correct 5 ms 9812 KB Output is correct
58 Correct 7 ms 9940 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9724 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 73 ms 22040 KB Output is correct
5 Correct 67 ms 24780 KB Output is correct
6 Correct 75 ms 26428 KB Output is correct
7 Correct 96 ms 29592 KB Output is correct
8 Correct 98 ms 29644 KB Output is correct
9 Correct 100 ms 29572 KB Output is correct
10 Correct 99 ms 29588 KB Output is correct
11 Correct 97 ms 29512 KB Output is correct
12 Correct 94 ms 29076 KB Output is correct
13 Correct 93 ms 29012 KB Output is correct
14 Correct 93 ms 29220 KB Output is correct
15 Correct 40 ms 25148 KB Output is correct
16 Correct 85 ms 27256 KB Output is correct
17 Correct 39 ms 14300 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 84 ms 15948 KB Output is correct
3 Correct 134 ms 17204 KB Output is correct
4 Correct 107 ms 17460 KB Output is correct
5 Correct 160 ms 21136 KB Output is correct
6 Correct 166 ms 21096 KB Output is correct
7 Correct 164 ms 21124 KB Output is correct
8 Correct 169 ms 21088 KB Output is correct
9 Correct 165 ms 21044 KB Output is correct
10 Correct 168 ms 21076 KB Output is correct
11 Correct 162 ms 21192 KB Output is correct
12 Correct 167 ms 21196 KB Output is correct
13 Correct 172 ms 21596 KB Output is correct
14 Correct 170 ms 22476 KB Output is correct
15 Correct 186 ms 22796 KB Output is correct
16 Correct 164 ms 21592 KB Output is correct
17 Correct 169 ms 21624 KB Output is correct
18 Correct 162 ms 21536 KB Output is correct
19 Correct 130 ms 18040 KB Output is correct
20 Correct 126 ms 18048 KB Output is correct
21 Correct 131 ms 17964 KB Output is correct
22 Correct 145 ms 18096 KB Output is correct
23 Correct 127 ms 18036 KB Output is correct
24 Correct 129 ms 18052 KB Output is correct
25 Correct 130 ms 18056 KB Output is correct
26 Correct 131 ms 18100 KB Output is correct
27 Correct 131 ms 18124 KB Output is correct
28 Correct 130 ms 17992 KB Output is correct
29 Correct 132 ms 18128 KB Output is correct
30 Correct 133 ms 18376 KB Output is correct
31 Correct 139 ms 18536 KB Output is correct
32 Correct 140 ms 18996 KB Output is correct
33 Correct 148 ms 19964 KB Output is correct
34 Correct 147 ms 20104 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9732 KB Output is correct
3 Correct 5 ms 9748 KB Output is correct
4 Correct 205 ms 20900 KB Output is correct
5 Correct 201 ms 20996 KB Output is correct
6 Correct 241 ms 24036 KB Output is correct
7 Correct 259 ms 25580 KB Output is correct
8 Correct 262 ms 25688 KB Output is correct
9 Correct 245 ms 25532 KB Output is correct
10 Correct 242 ms 25580 KB Output is correct
11 Correct 254 ms 25500 KB Output is correct
12 Correct 244 ms 25548 KB Output is correct
13 Correct 253 ms 25552 KB Output is correct
14 Correct 39 ms 14420 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 4 ms 9736 KB Output is correct
15 Correct 4 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9708 KB Output is correct
18 Correct 4 ms 9684 KB Output is correct
19 Correct 4 ms 9684 KB Output is correct
20 Correct 5 ms 9736 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 4 ms 9696 KB Output is correct
23 Correct 5 ms 9684 KB Output is correct
24 Correct 5 ms 9684 KB Output is correct
25 Correct 5 ms 9684 KB Output is correct
26 Correct 5 ms 9736 KB Output is correct
27 Correct 4 ms 9732 KB Output is correct
28 Correct 4 ms 9684 KB Output is correct
29 Correct 5 ms 9736 KB Output is correct
30 Correct 9 ms 10068 KB Output is correct
31 Correct 7 ms 9892 KB Output is correct
32 Correct 7 ms 10004 KB Output is correct
33 Correct 7 ms 9940 KB Output is correct
34 Correct 7 ms 9940 KB Output is correct
35 Correct 7 ms 9940 KB Output is correct
36 Correct 7 ms 10000 KB Output is correct
37 Correct 6 ms 9940 KB Output is correct
38 Correct 6 ms 10068 KB Output is correct
39 Correct 6 ms 10068 KB Output is correct
40 Correct 6 ms 9992 KB Output is correct
41 Correct 6 ms 10068 KB Output is correct
42 Correct 6 ms 10068 KB Output is correct
43 Correct 6 ms 9940 KB Output is correct
44 Correct 6 ms 9940 KB Output is correct
45 Correct 6 ms 9940 KB Output is correct
46 Correct 7 ms 9936 KB Output is correct
47 Correct 7 ms 9940 KB Output is correct
48 Correct 6 ms 9976 KB Output is correct
49 Correct 9 ms 10068 KB Output is correct
50 Correct 6 ms 9940 KB Output is correct
51 Correct 6 ms 9940 KB Output is correct
52 Correct 6 ms 9940 KB Output is correct
53 Correct 6 ms 9940 KB Output is correct
54 Correct 6 ms 9996 KB Output is correct
55 Correct 6 ms 9940 KB Output is correct
56 Correct 6 ms 9812 KB Output is correct
57 Correct 5 ms 9812 KB Output is correct
58 Correct 7 ms 9940 KB Output is correct
59 Correct 4 ms 9684 KB Output is correct
60 Correct 4 ms 9724 KB Output is correct
61 Correct 5 ms 9812 KB Output is correct
62 Correct 73 ms 22040 KB Output is correct
63 Correct 67 ms 24780 KB Output is correct
64 Correct 75 ms 26428 KB Output is correct
65 Correct 96 ms 29592 KB Output is correct
66 Correct 98 ms 29644 KB Output is correct
67 Correct 100 ms 29572 KB Output is correct
68 Correct 99 ms 29588 KB Output is correct
69 Correct 97 ms 29512 KB Output is correct
70 Correct 94 ms 29076 KB Output is correct
71 Correct 93 ms 29012 KB Output is correct
72 Correct 93 ms 29220 KB Output is correct
73 Correct 40 ms 25148 KB Output is correct
74 Correct 85 ms 27256 KB Output is correct
75 Correct 39 ms 14300 KB Output is correct
76 Correct 4 ms 9684 KB Output is correct
77 Correct 84 ms 15948 KB Output is correct
78 Correct 134 ms 17204 KB Output is correct
79 Correct 107 ms 17460 KB Output is correct
80 Correct 160 ms 21136 KB Output is correct
81 Correct 166 ms 21096 KB Output is correct
82 Correct 164 ms 21124 KB Output is correct
83 Correct 169 ms 21088 KB Output is correct
84 Correct 165 ms 21044 KB Output is correct
85 Correct 168 ms 21076 KB Output is correct
86 Correct 162 ms 21192 KB Output is correct
87 Correct 167 ms 21196 KB Output is correct
88 Correct 172 ms 21596 KB Output is correct
89 Correct 170 ms 22476 KB Output is correct
90 Correct 186 ms 22796 KB Output is correct
91 Correct 164 ms 21592 KB Output is correct
92 Correct 169 ms 21624 KB Output is correct
93 Correct 162 ms 21536 KB Output is correct
94 Correct 130 ms 18040 KB Output is correct
95 Correct 126 ms 18048 KB Output is correct
96 Correct 131 ms 17964 KB Output is correct
97 Correct 145 ms 18096 KB Output is correct
98 Correct 127 ms 18036 KB Output is correct
99 Correct 129 ms 18052 KB Output is correct
100 Correct 130 ms 18056 KB Output is correct
101 Correct 131 ms 18100 KB Output is correct
102 Correct 131 ms 18124 KB Output is correct
103 Correct 130 ms 17992 KB Output is correct
104 Correct 132 ms 18128 KB Output is correct
105 Correct 133 ms 18376 KB Output is correct
106 Correct 139 ms 18536 KB Output is correct
107 Correct 140 ms 18996 KB Output is correct
108 Correct 148 ms 19964 KB Output is correct
109 Correct 147 ms 20104 KB Output is correct
110 Correct 4 ms 9684 KB Output is correct
111 Correct 4 ms 9732 KB Output is correct
112 Correct 5 ms 9748 KB Output is correct
113 Correct 205 ms 20900 KB Output is correct
114 Correct 201 ms 20996 KB Output is correct
115 Correct 241 ms 24036 KB Output is correct
116 Correct 259 ms 25580 KB Output is correct
117 Correct 262 ms 25688 KB Output is correct
118 Correct 245 ms 25532 KB Output is correct
119 Correct 242 ms 25580 KB Output is correct
120 Correct 254 ms 25500 KB Output is correct
121 Correct 244 ms 25548 KB Output is correct
122 Correct 253 ms 25552 KB Output is correct
123 Correct 39 ms 14420 KB Output is correct
124 Correct 164 ms 24524 KB Output is correct
125 Correct 131 ms 22152 KB Output is correct
126 Correct 196 ms 25220 KB Output is correct
127 Correct 204 ms 25156 KB Output is correct
128 Correct 192 ms 25164 KB Output is correct
129 Correct 193 ms 25148 KB Output is correct
130 Correct 197 ms 25204 KB Output is correct
131 Correct 101 ms 28356 KB Output is correct
132 Correct 101 ms 29432 KB Output is correct
133 Correct 99 ms 25652 KB Output is correct
134 Correct 154 ms 22180 KB Output is correct
135 Correct 160 ms 22208 KB Output is correct
136 Correct 159 ms 22124 KB Output is correct
137 Correct 97 ms 26048 KB Output is correct
138 Correct 89 ms 26056 KB Output is correct
139 Correct 104 ms 26120 KB Output is correct
140 Correct 92 ms 26044 KB Output is correct
141 Correct 86 ms 26108 KB Output is correct
142 Correct 88 ms 26096 KB Output is correct
143 Correct 44 ms 17380 KB Output is correct
144 Correct 182 ms 22784 KB Output is correct