oj.uz

Submission #824816

# Submission time Handle Problem Language Result Execution time Memory
824816 2023-08-14T10:47:46 Z grogu Tourism (JOI23_tourism) C++14
28 / 100
 5000 ms 33156 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll array<ll,3>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;


#define maxn 100005
#define lg 21
ll n,m,q;
vector<ll> g[maxn];
ll st[lg][maxn];
ll in[maxn],out[maxn],ti = 0;
ll rev[maxn];
ll dub[maxn];
ll c[maxn];
pll a[maxn];
void dfs(ll u,ll p){
    st[0][u] = p;
    dub[u] = dub[p] + 1;
    in[u] = ++ti;
    rev[ti] = u;
    for(ll s : g[u]){
        if(s==p) continue;
        dfs(s,u);
    }
    out[u] = ti-1;
}
bool intree(ll x,ll y){return in[y]<=in[x]&&out[y]>=out[x];}
ll lca(ll x,ll y){
    if(intree(x,y)) return y;
    if(intree(y,x)) return x;
    for(ll j = lg-1;j>=0;j--){
        if(!intree(x,st[j][y])) y = st[j][y];
    }
    return st[0][y];
}
ll dis(ll x,ll y){
    return dub[x] + dub[y] - 2*dub[lca(x,y)];
}
ll d = 300;
bool cmp(pll x,pll y){
    if(x[0]/d!=y[0]/d) return x[0]/d<y[0]/d;
    return x[1]<y[1];
}
multiset<ll> s;
ll ans = 0;
void add(ll i){
    ll x = c[i];
    s.insert(in[x]);
    auto it = s.lower_bound(in[x]);
    ll y = -1,z = -1;
    if(it!=s.begin()){
        it--;
        y = rev[*it];
        ans+=dis(x,y);
        it++;
    }
    it++;
    if(it!=s.end()){
        z = rev[*it];
        ans+=dis(x,z);
    }
    if(z!=-1&&y!=-1) ans-=dis(z,y);
}
void del(ll i){
    ll x = c[i];
    auto it = s.lower_bound(in[x]);
    ll y = -1,z = -1;
    if(it!=s.begin()){
        it--;
        y = rev[*it];
        ans-=dis(x,y);
        it++;
    }
    it++;
    if(it!=s.end()){
        z = rev[*it];
        ans-=dis(x,z);
    }
    if(z!=-1&&y!=-1) ans+=dis(z,y);
    it--;
    s.erase(it);
}
ll rez[maxn];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m >> q;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1,1);
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[j][i] = st[j-1][st[j-1][i]];
    for(ll i = 1;i<=m;i++) cin >> c[i];
    for(ll i = 1;i<=q;i++) cin >> a[i][0] >> a[i][1];
    for(ll i = 1;i<=q;i++) a[i][2] = i;
    sort(a+1,a+1+q,cmp);
    ll tl = 1,tr = 1;
    add(1);
    for(ll i = 1;i<=q;i++){
        while(tr<a[i][1]) add(++tr);
        while(tl>a[i][0]) add(--tl);
        while(tl<a[i][0]) del(tl++);
        while(tr>a[i][1]) del(tr--);
        ll y = rev[*s.begin()];
        ll z = rev[*prev(s.end())];
        rez[a[i][2]] = ans + dis(y,z);
    }
    for(ll i = 1;i<=q;i++){
        cout<<rez[i]/2 + 1<<endl;
    }
	return (0-0);
}
/**
7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 3
4 6
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 5 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 5 ms 2900 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 7 ms 2900 KB Output is correct
11 Correct 7 ms 2936 KB Output is correct
12 Correct 2 ms 2816 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 4 ms 2936 KB Output is correct
17 Correct 4 ms 2900 KB Output is correct
18 Correct 5 ms 2824 KB Output is correct
19 Correct 4 ms 2900 KB Output is correct
20 Correct 5 ms 2900 KB Output is correct
21 Correct 10 ms 2940 KB Output is correct
22 Correct 8 ms 2812 KB Output is correct
23 Correct 7 ms 2944 KB Output is correct
24 Correct 12 ms 2816 KB Output is correct
25 Correct 10 ms 2940 KB Output is correct
26 Correct 8 ms 2900 KB Output is correct
27 Correct 2 ms 2808 KB Output is correct
28 Correct 2 ms 2864 KB Output is correct
29 Correct 2 ms 2900 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 5 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 5 ms 2900 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 7 ms 2900 KB Output is correct
11 Correct 7 ms 2936 KB Output is correct
12 Correct 2 ms 2816 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 4 ms 2936 KB Output is correct
17 Correct 4 ms 2900 KB Output is correct
18 Correct 5 ms 2824 KB Output is correct
19 Correct 4 ms 2900 KB Output is correct
20 Correct 5 ms 2900 KB Output is correct
21 Correct 10 ms 2940 KB Output is correct
22 Correct 8 ms 2812 KB Output is correct
23 Correct 7 ms 2944 KB Output is correct
24 Correct 12 ms 2816 KB Output is correct
25 Correct 10 ms 2940 KB Output is correct
26 Correct 8 ms 2900 KB Output is correct
27 Correct 2 ms 2808 KB Output is correct
28 Correct 2 ms 2864 KB Output is correct
29 Correct 2 ms 2900 KB Output is correct
30 Correct 54 ms 3304 KB Output is correct
31 Correct 64 ms 3320 KB Output is correct
32 Correct 82 ms 3412 KB Output is correct
33 Correct 85 ms 3492 KB Output is correct
34 Correct 99 ms 3512 KB Output is correct
35 Correct 10 ms 3412 KB Output is correct
36 Correct 10 ms 3520 KB Output is correct
37 Correct 10 ms 3516 KB Output is correct
38 Correct 25 ms 3556 KB Output is correct
39 Correct 25 ms 3552 KB Output is correct
40 Correct 27 ms 3532 KB Output is correct
41 Correct 5 ms 3540 KB Output is correct
42 Correct 5 ms 3588 KB Output is correct
43 Correct 5 ms 3540 KB Output is correct
44 Correct 31 ms 3524 KB Output is correct
45 Correct 36 ms 3500 KB Output is correct
46 Correct 31 ms 3468 KB Output is correct
47 Correct 5 ms 3540 KB Output is correct
48 Correct 5 ms 3412 KB Output is correct
49 Correct 5 ms 3528 KB Output is correct
50 Correct 109 ms 3500 KB Output is correct
51 Correct 86 ms 3504 KB Output is correct
52 Correct 95 ms 3508 KB Output is correct
53 Correct 87 ms 3612 KB Output is correct
54 Correct 88 ms 3504 KB Output is correct
55 Correct 86 ms 3412 KB Output is correct
56 Correct 12 ms 2900 KB Output is correct
57 Correct 2 ms 3284 KB Output is correct
58 Correct 4 ms 3412 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2812 KB Output is correct
2 Correct 2 ms 2812 KB Output is correct
3 Correct 13 ms 3020 KB Output is correct
4 Execution timed out 5052 ms 27104 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 139 ms 16996 KB Output is correct
3 Correct 196 ms 18580 KB Output is correct
4 Correct 229 ms 20300 KB Output is correct
5 Correct 304 ms 33156 KB Output is correct
6 Correct 458 ms 31624 KB Output is correct
7 Correct 591 ms 29432 KB Output is correct
8 Correct 502 ms 28816 KB Output is correct
9 Correct 452 ms 28584 KB Output is correct
10 Correct 459 ms 28540 KB Output is correct
11 Correct 354 ms 28620 KB Output is correct
12 Correct 337 ms 28624 KB Output is correct
13 Correct 296 ms 28872 KB Output is correct
14 Correct 263 ms 29824 KB Output is correct
15 Correct 313 ms 32928 KB Output is correct
16 Correct 437 ms 31040 KB Output is correct
17 Correct 446 ms 31016 KB Output is correct
18 Correct 403 ms 31024 KB Output is correct
19 Correct 94 ms 32596 KB Output is correct
20 Correct 119 ms 32560 KB Output is correct
21 Correct 135 ms 29808 KB Output is correct
22 Correct 160 ms 28880 KB Output is correct
23 Correct 163 ms 28460 KB Output is correct
24 Correct 216 ms 28168 KB Output is correct
25 Correct 329 ms 28128 KB Output is correct
26 Correct 312 ms 28056 KB Output is correct
27 Correct 357 ms 28020 KB Output is correct
28 Correct 389 ms 28020 KB Output is correct
29 Correct 358 ms 28068 KB Output is correct
30 Correct 319 ms 28184 KB Output is correct
31 Correct 340 ms 28368 KB Output is correct
32 Correct 269 ms 28836 KB Output is correct
33 Correct 265 ms 30204 KB Output is correct
34 Correct 325 ms 32476 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 12 ms 3020 KB Output is correct
4 Execution timed out 5076 ms 26028 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 1 ms 2812 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 5 ms 2772 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 5 ms 2900 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 7 ms 2900 KB Output is correct
11 Correct 7 ms 2936 KB Output is correct
12 Correct 2 ms 2816 KB Output is correct
13 Correct 3 ms 3028 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 4 ms 2944 KB Output is correct
16 Correct 4 ms 2936 KB Output is correct
17 Correct 4 ms 2900 KB Output is correct
18 Correct 5 ms 2824 KB Output is correct
19 Correct 4 ms 2900 KB Output is correct
20 Correct 5 ms 2900 KB Output is correct
21 Correct 10 ms 2940 KB Output is correct
22 Correct 8 ms 2812 KB Output is correct
23 Correct 7 ms 2944 KB Output is correct
24 Correct 12 ms 2816 KB Output is correct
25 Correct 10 ms 2940 KB Output is correct
26 Correct 8 ms 2900 KB Output is correct
27 Correct 2 ms 2808 KB Output is correct
28 Correct 2 ms 2864 KB Output is correct
29 Correct 2 ms 2900 KB Output is correct
30 Correct 54 ms 3304 KB Output is correct
31 Correct 64 ms 3320 KB Output is correct
32 Correct 82 ms 3412 KB Output is correct
33 Correct 85 ms 3492 KB Output is correct
34 Correct 99 ms 3512 KB Output is correct
35 Correct 10 ms 3412 KB Output is correct
36 Correct 10 ms 3520 KB Output is correct
37 Correct 10 ms 3516 KB Output is correct
38 Correct 25 ms 3556 KB Output is correct
39 Correct 25 ms 3552 KB Output is correct
40 Correct 27 ms 3532 KB Output is correct
41 Correct 5 ms 3540 KB Output is correct
42 Correct 5 ms 3588 KB Output is correct
43 Correct 5 ms 3540 KB Output is correct
44 Correct 31 ms 3524 KB Output is correct
45 Correct 36 ms 3500 KB Output is correct
46 Correct 31 ms 3468 KB Output is correct
47 Correct 5 ms 3540 KB Output is correct
48 Correct 5 ms 3412 KB Output is correct
49 Correct 5 ms 3528 KB Output is correct
50 Correct 109 ms 3500 KB Output is correct
51 Correct 86 ms 3504 KB Output is correct
52 Correct 95 ms 3508 KB Output is correct
53 Correct 87 ms 3612 KB Output is correct
54 Correct 88 ms 3504 KB Output is correct
55 Correct 86 ms 3412 KB Output is correct
56 Correct 12 ms 2900 KB Output is correct
57 Correct 2 ms 3284 KB Output is correct
58 Correct 4 ms 3412 KB Output is correct
59 Correct 1 ms 2812 KB Output is correct
60 Correct 2 ms 2812 KB Output is correct
61 Correct 13 ms 3020 KB Output is correct
62 Execution timed out 5052 ms 27104 KB Time limit exceeded
63 Halted 0 ms 0 KB -