oj.uz

Submission #824834

# Submission time Handle Problem Language Result Execution time Memory
824834 2023-08-14T11:00:22 Z grogu Tourism (JOI23_tourism) C++14
28 / 100
 5000 ms 20744 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#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 = 1000;
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 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 6 ms 2772 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2836 KB Output is correct
9 Correct 7 ms 2844 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2772 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 4 ms 2772 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 4 ms 2772 KB Output is correct
20 Correct 4 ms 2772 KB Output is correct
21 Correct 8 ms 2852 KB Output is correct
22 Correct 8 ms 2852 KB Output is correct
23 Correct 7 ms 2864 KB Output is correct
24 Correct 7 ms 2772 KB Output is correct
25 Correct 8 ms 2772 KB Output is correct
26 Correct 8 ms 2772 KB Output is correct
27 Correct 3 ms 2772 KB Output is correct
28 Correct 1 ms 2772 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 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 6 ms 2772 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2836 KB Output is correct
9 Correct 7 ms 2844 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2772 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 4 ms 2772 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 4 ms 2772 KB Output is correct
20 Correct 4 ms 2772 KB Output is correct
21 Correct 8 ms 2852 KB Output is correct
22 Correct 8 ms 2852 KB Output is correct
23 Correct 7 ms 2864 KB Output is correct
24 Correct 7 ms 2772 KB Output is correct
25 Correct 8 ms 2772 KB Output is correct
26 Correct 8 ms 2772 KB Output is correct
27 Correct 3 ms 2772 KB Output is correct
28 Correct 1 ms 2772 KB Output is correct
29 Correct 2 ms 2900 KB Output is correct
30 Correct 128 ms 3056 KB Output is correct
31 Correct 164 ms 3080 KB Output is correct
32 Correct 214 ms 3120 KB Output is correct
33 Correct 204 ms 3148 KB Output is correct
34 Correct 219 ms 3164 KB Output is correct
35 Correct 13 ms 3156 KB Output is correct
36 Correct 10 ms 3188 KB Output is correct
37 Correct 9 ms 3180 KB Output is correct
38 Correct 71 ms 3216 KB Output is correct
39 Correct 70 ms 3308 KB Output is correct
40 Correct 69 ms 3192 KB Output is correct
41 Correct 5 ms 3156 KB Output is correct
42 Correct 5 ms 3268 KB Output is correct
43 Correct 5 ms 3156 KB Output is correct
44 Correct 89 ms 3172 KB Output is correct
45 Correct 82 ms 3152 KB Output is correct
46 Correct 84 ms 3172 KB Output is correct
47 Correct 5 ms 3204 KB Output is correct
48 Correct 5 ms 3156 KB Output is correct
49 Correct 5 ms 3156 KB Output is correct
50 Correct 236 ms 3168 KB Output is correct
51 Correct 227 ms 3264 KB Output is correct
52 Correct 225 ms 3148 KB Output is correct
53 Correct 233 ms 3152 KB Output is correct
54 Correct 233 ms 3136 KB Output is correct
55 Correct 221 ms 3172 KB Output is correct
56 Correct 29 ms 2920 KB Output is correct
57 Correct 2 ms 3028 KB Output is correct
58 Correct 3 ms 3068 KB Output is correct

Subtask #3
0 / 7.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 33 ms 2892 KB Output is correct
4 Execution timed out 5050 ms 18072 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 96 ms 10160 KB Output is correct
3 Correct 154 ms 10872 KB Output is correct
4 Correct 125 ms 11864 KB Output is correct
5 Correct 181 ms 20708 KB Output is correct
6 Correct 258 ms 19216 KB Output is correct
7 Correct 328 ms 17100 KB Output is correct
8 Correct 303 ms 16364 KB Output is correct
9 Correct 296 ms 16204 KB Output is correct
10 Correct 264 ms 16084 KB Output is correct
11 Correct 267 ms 16228 KB Output is correct
12 Correct 187 ms 16028 KB Output is correct
13 Correct 179 ms 16204 KB Output is correct
14 Correct 166 ms 16608 KB Output is correct
15 Correct 171 ms 17884 KB Output is correct
16 Correct 296 ms 18292 KB Output is correct
17 Correct 273 ms 18328 KB Output is correct
18 Correct 230 ms 18372 KB Output is correct
19 Correct 83 ms 20724 KB Output is correct
20 Correct 97 ms 20744 KB Output is correct
21 Correct 121 ms 17924 KB Output is correct
22 Correct 145 ms 17080 KB Output is correct
23 Correct 123 ms 16532 KB Output is correct
24 Correct 148 ms 16172 KB Output is correct
25 Correct 205 ms 16104 KB Output is correct
26 Correct 236 ms 16204 KB Output is correct
27 Correct 321 ms 16092 KB Output is correct
28 Correct 295 ms 16052 KB Output is correct
29 Correct 235 ms 15996 KB Output is correct
30 Correct 227 ms 16268 KB Output is correct
31 Correct 243 ms 16308 KB Output is correct
32 Correct 280 ms 16416 KB Output is correct
33 Correct 227 ms 16940 KB Output is correct
34 Correct 194 ms 17832 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 29 ms 2908 KB Output is correct
4 Execution timed out 5019 ms 16024 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 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 6 ms 2772 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 4 ms 2772 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 3 ms 2836 KB Output is correct
9 Correct 7 ms 2844 KB Output is correct
10 Correct 6 ms 2772 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2772 KB Output is correct
15 Correct 4 ms 2772 KB Output is correct
16 Correct 4 ms 2772 KB Output is correct
17 Correct 4 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 4 ms 2772 KB Output is correct
20 Correct 4 ms 2772 KB Output is correct
21 Correct 8 ms 2852 KB Output is correct
22 Correct 8 ms 2852 KB Output is correct
23 Correct 7 ms 2864 KB Output is correct
24 Correct 7 ms 2772 KB Output is correct
25 Correct 8 ms 2772 KB Output is correct
26 Correct 8 ms 2772 KB Output is correct
27 Correct 3 ms 2772 KB Output is correct
28 Correct 1 ms 2772 KB Output is correct
29 Correct 2 ms 2900 KB Output is correct
30 Correct 128 ms 3056 KB Output is correct
31 Correct 164 ms 3080 KB Output is correct
32 Correct 214 ms 3120 KB Output is correct
33 Correct 204 ms 3148 KB Output is correct
34 Correct 219 ms 3164 KB Output is correct
35 Correct 13 ms 3156 KB Output is correct
36 Correct 10 ms 3188 KB Output is correct
37 Correct 9 ms 3180 KB Output is correct
38 Correct 71 ms 3216 KB Output is correct
39 Correct 70 ms 3308 KB Output is correct
40 Correct 69 ms 3192 KB Output is correct
41 Correct 5 ms 3156 KB Output is correct
42 Correct 5 ms 3268 KB Output is correct
43 Correct 5 ms 3156 KB Output is correct
44 Correct 89 ms 3172 KB Output is correct
45 Correct 82 ms 3152 KB Output is correct
46 Correct 84 ms 3172 KB Output is correct
47 Correct 5 ms 3204 KB Output is correct
48 Correct 5 ms 3156 KB Output is correct
49 Correct 5 ms 3156 KB Output is correct
50 Correct 236 ms 3168 KB Output is correct
51 Correct 227 ms 3264 KB Output is correct
52 Correct 225 ms 3148 KB Output is correct
53 Correct 233 ms 3152 KB Output is correct
54 Correct 233 ms 3136 KB Output is correct
55 Correct 221 ms 3172 KB Output is correct
56 Correct 29 ms 2920 KB Output is correct
57 Correct 2 ms 3028 KB Output is correct
58 Correct 3 ms 3068 KB Output is correct
59 Correct 1 ms 2772 KB Output is correct
60 Correct 2 ms 2772 KB Output is correct
61 Correct 33 ms 2892 KB Output is correct
62 Execution timed out 5050 ms 18072 KB Time limit exceeded
63 Halted 0 ms 0 KB -