oj.uz

Submission #1037630

# Submission time Handle Problem Language Result Execution time Memory
1037630 2024-07-29T06:14:47 Z 변재우(#10984) Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 33364 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010, sqrtN=500, S=1<<17;
int N, M, Q, C[Nmax], p, L[Nmax], R[Nmax], D[Nmax], P[20][Nmax];
int curr, par, cnt[Nmax], ans[Nmax];
vector<int> adj[Nmax];
struct Query {int l, r, i;}X[Nmax];

int LCA(int u, int v) {
    if(!u || !v) return 0;
    if(D[u]<D[v]) swap(u, v);
    for(int i=16; i>=0; i--) if(D[P[i][u]]>D[v]) u=P[i][u];
    if(D[u]!=D[v]) u=P[0][u];
    for(int i=16; i>=0; i--) if(P[i][u]!=P[i][v]) u=P[i][u], v=P[i][v];
    if(u!=v) u=P[0][u];
    return u;
}

class Seg {
public:
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    int Query(int l, int r) {return Query(1, 1, S, l, r);}
private:
    int Tree[2*S];
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            Tree[node]=v;
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Tree[node]=Tree[lch]+Tree[rch];
    }
    int Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return 0;
        if(l<=s && e<=r) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return Query(lch, s, m, l, r)+Query(rch, m+1, e, l, r);
    }
}T;

class LSeg {
public:
    void Update(int k, int v) {Update(1, 1, S, k, v);}
    int Query(int l, int r) {return Query(1, 1, S, l, r);}
private:
    int Tree[2*S];
    void Update(int node, int s, int e, int k, int v) {
        if(s==e) {
            Tree[node]=v;
            return;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, v);
        else Update(rch, m+1, e, k, v);
        Tree[node]=LCA(Tree[lch], Tree[rch]);
    }
    int Query(int node, int s, int e, int l, int r) {
        if(s>r || l>e) return 0;
        if(l<=s && e<=r) return Tree[node];
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(r<=m) return Query(lch, s, m, l, r);
        if(l>=m+1) return Query(rch, m+1, e, l, r);
        return LCA(Query(lch, s, m, l, r), Query(rch, m+1, e, l, r));
    }
}TL;

void DFS(int curr, int prev) {
    L[curr]=++p;
    for(int next:adj[curr]) if(next!=prev) D[next]=D[curr]+1, P[0][next]=curr, DFS(next, curr);
    R[curr]=p;
}


void Add(int x) {
    if(!par) {
        par=x, curr=1;
        cnt[x]++, T.Update(L[x], 1);
        return;
    }
    cnt[x]++;
    if(cnt[x]>1) return;
    if(!T.Query(L[x], R[x])) {
        int y=x;
        for(int i=16; i>=0; i--) if(P[i][y] && !T.Query(L[P[i][y]], R[P[i][y]])) y=P[i][y];
        y=P[0][y];
        curr+=D[x]-D[y];
    }
    T.Update(L[x], 1);
    int np=LCA(par, x);
    curr+=D[par]-D[np], par=np;
    return;
}

void Delete(int x, int tl, int tr) {
    cnt[x]--;
    if(cnt[x]) return;
    T.Update(L[x], 0);
    if(!T.Query(L[x], R[x])) {
        int y=x;
        for(int i=16; i>=0; i--) if(P[i][y] && !T.Query(L[P[i][y]], R[P[i][y]])) y=P[i][y];
        y=P[0][y];
        curr-=D[x]-D[y];
        // cout<<"asdf"<<D[x]-D[y]<<"\n";
    }
    int np=TL.Query(tl, tr);
    // cout<<"qwer"<<tl<<"~"<<tr<<"\n";
    // cout<<"qwer"<<par<<" -> "<<np<<"\n";
    curr-=D[np]-D[par], par=np;
    return;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>Q;
    for(int i=1; i<N; i++) {
        int u, v; cin>>u>>v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    DFS(1, 0);
    for(int i=1; i<20; i++) for(int j=1; j<=N; j++) P[i][j]=P[i-1][P[i-1][j]];
    for(int i=1; i<=M; i++) cin>>C[i], TL.Update(i, C[i]);
    for(int i=1; i<=Q; i++) cin>>X[i].l>>X[i].r, X[i].i=i;
    sort(X+1, X+Q+1, [](Query a, Query b) {return ((a.l/sqrtN)!=(b.l/sqrtN))?((a.l/sqrtN)<(b.l/sqrtN)):(a.r<b.r);});
    for(int i=X[1].l; i<=X[1].r; i++) Add(C[i]);
    ans[X[1].i]=curr;
    // cout<<X[1].l<<"~"<<X[1].r<<": "<<curr<<"\n";
    for(int i=2, l=X[1].l, r=X[1].r; i<=Q; i++) {
        while(l>X[i].l) Add(C[--l]);
        while(r<X[i].r) Add(C[++r]);
        // cout<<curr<<"\n";
        while(l<X[i].l) Delete(C[l], l+1, r), l++;
        while(r>X[i].r) Delete(C[r], l, r-1), r--;
        ans[X[i].i]=curr;
        // cout<<X[i].l<<"~"<<X[i].r<<": "<<curr<<"\n";
    }
    for(int i=1; i<=Q; i++) cout<<ans[i]<<"\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 2 ms 22876 KB Output is correct
3 Correct 3 ms 23092 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 6 ms 22876 KB Output is correct
6 Correct 8 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 6 ms 22876 KB Output is correct
9 Correct 12 ms 23064 KB Output is correct
10 Correct 12 ms 22872 KB Output is correct
11 Correct 11 ms 22876 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 23072 KB Output is correct
15 Correct 11 ms 22876 KB Output is correct
16 Correct 10 ms 22876 KB Output is correct
17 Correct 9 ms 22876 KB Output is correct
18 Correct 11 ms 22876 KB Output is correct
19 Correct 11 ms 23112 KB Output is correct
20 Correct 10 ms 22876 KB Output is correct
21 Correct 11 ms 23116 KB Output is correct
22 Correct 13 ms 22872 KB Output is correct
23 Correct 10 ms 22876 KB Output is correct
24 Correct 12 ms 23112 KB Output is correct
25 Correct 12 ms 22876 KB Output is correct
26 Correct 16 ms 22876 KB Output is correct
27 Correct 3 ms 24924 KB Output is correct
28 Correct 2 ms 22876 KB Output is correct
29 Correct 3 ms 22876 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 2 ms 22876 KB Output is correct
3 Correct 3 ms 23092 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 6 ms 22876 KB Output is correct
6 Correct 8 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 6 ms 22876 KB Output is correct
9 Correct 12 ms 23064 KB Output is correct
10 Correct 12 ms 22872 KB Output is correct
11 Correct 11 ms 22876 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 23072 KB Output is correct
15 Correct 11 ms 22876 KB Output is correct
16 Correct 10 ms 22876 KB Output is correct
17 Correct 9 ms 22876 KB Output is correct
18 Correct 11 ms 22876 KB Output is correct
19 Correct 11 ms 23112 KB Output is correct
20 Correct 10 ms 22876 KB Output is correct
21 Correct 11 ms 23116 KB Output is correct
22 Correct 13 ms 22872 KB Output is correct
23 Correct 10 ms 22876 KB Output is correct
24 Correct 12 ms 23112 KB Output is correct
25 Correct 12 ms 22876 KB Output is correct
26 Correct 16 ms 22876 KB Output is correct
27 Correct 3 ms 24924 KB Output is correct
28 Correct 2 ms 22876 KB Output is correct
29 Correct 3 ms 22876 KB Output is correct
30 Correct 141 ms 23128 KB Output is correct
31 Correct 203 ms 23128 KB Output is correct
32 Correct 225 ms 23132 KB Output is correct
33 Correct 240 ms 23212 KB Output is correct
34 Correct 233 ms 23224 KB Output is correct
35 Correct 15 ms 23228 KB Output is correct
36 Correct 18 ms 23240 KB Output is correct
37 Correct 15 ms 23236 KB Output is correct
38 Correct 163 ms 23284 KB Output is correct
39 Correct 174 ms 23132 KB Output is correct
40 Correct 177 ms 23384 KB Output is correct
41 Correct 16 ms 23336 KB Output is correct
42 Correct 14 ms 23132 KB Output is correct
43 Correct 16 ms 23228 KB Output is correct
44 Correct 182 ms 23260 KB Output is correct
45 Correct 176 ms 23132 KB Output is correct
46 Correct 203 ms 23252 KB Output is correct
47 Correct 12 ms 23132 KB Output is correct
48 Correct 16 ms 23240 KB Output is correct
49 Correct 16 ms 23272 KB Output is correct
50 Correct 193 ms 23132 KB Output is correct
51 Correct 188 ms 23220 KB Output is correct
52 Correct 173 ms 23232 KB Output is correct
53 Correct 169 ms 23220 KB Output is correct
54 Correct 170 ms 23224 KB Output is correct
55 Correct 193 ms 23128 KB Output is correct
56 Correct 4 ms 24924 KB Output is correct
57 Correct 3 ms 23132 KB Output is correct
58 Correct 6 ms 23132 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 22876 KB Output is correct
2 Correct 2 ms 24924 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Execution timed out 5096 ms 32940 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 168 ms 27428 KB Output is correct
3 Correct 266 ms 27984 KB Output is correct
4 Correct 203 ms 28500 KB Output is correct
5 Correct 118 ms 31060 KB Output is correct
6 Correct 263 ms 31056 KB Output is correct
7 Correct 332 ms 31240 KB Output is correct
8 Correct 416 ms 31132 KB Output is correct
9 Correct 364 ms 31176 KB Output is correct
10 Correct 368 ms 31160 KB Output is correct
11 Correct 334 ms 31060 KB Output is correct
12 Correct 296 ms 31072 KB Output is correct
13 Correct 296 ms 33136 KB Output is correct
14 Correct 297 ms 33320 KB Output is correct
15 Correct 268 ms 33364 KB Output is correct
16 Correct 283 ms 33108 KB Output is correct
17 Correct 295 ms 33108 KB Output is correct
18 Correct 268 ms 33108 KB Output is correct
19 Correct 124 ms 30760 KB Output is correct
20 Correct 167 ms 30544 KB Output is correct
21 Correct 274 ms 30544 KB Output is correct
22 Correct 293 ms 30544 KB Output is correct
23 Correct 364 ms 30652 KB Output is correct
24 Correct 411 ms 30728 KB Output is correct
25 Correct 408 ms 30636 KB Output is correct
26 Correct 501 ms 31060 KB Output is correct
27 Correct 462 ms 30800 KB Output is correct
28 Correct 486 ms 30760 KB Output is correct
29 Correct 510 ms 30784 KB Output is correct
30 Correct 540 ms 30804 KB Output is correct
31 Correct 492 ms 32840 KB Output is correct
32 Correct 502 ms 32720 KB Output is correct
33 Correct 475 ms 32848 KB Output is correct
34 Correct 548 ms 33068 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 22872 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Execution timed out 5030 ms 29776 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 2 ms 22876 KB Output is correct
3 Correct 3 ms 23092 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 6 ms 22876 KB Output is correct
6 Correct 8 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 6 ms 22876 KB Output is correct
9 Correct 12 ms 23064 KB Output is correct
10 Correct 12 ms 22872 KB Output is correct
11 Correct 11 ms 22876 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 3 ms 22876 KB Output is correct
14 Correct 3 ms 23072 KB Output is correct
15 Correct 11 ms 22876 KB Output is correct
16 Correct 10 ms 22876 KB Output is correct
17 Correct 9 ms 22876 KB Output is correct
18 Correct 11 ms 22876 KB Output is correct
19 Correct 11 ms 23112 KB Output is correct
20 Correct 10 ms 22876 KB Output is correct
21 Correct 11 ms 23116 KB Output is correct
22 Correct 13 ms 22872 KB Output is correct
23 Correct 10 ms 22876 KB Output is correct
24 Correct 12 ms 23112 KB Output is correct
25 Correct 12 ms 22876 KB Output is correct
26 Correct 16 ms 22876 KB Output is correct
27 Correct 3 ms 24924 KB Output is correct
28 Correct 2 ms 22876 KB Output is correct
29 Correct 3 ms 22876 KB Output is correct
30 Correct 141 ms 23128 KB Output is correct
31 Correct 203 ms 23128 KB Output is correct
32 Correct 225 ms 23132 KB Output is correct
33 Correct 240 ms 23212 KB Output is correct
34 Correct 233 ms 23224 KB Output is correct
35 Correct 15 ms 23228 KB Output is correct
36 Correct 18 ms 23240 KB Output is correct
37 Correct 15 ms 23236 KB Output is correct
38 Correct 163 ms 23284 KB Output is correct
39 Correct 174 ms 23132 KB Output is correct
40 Correct 177 ms 23384 KB Output is correct
41 Correct 16 ms 23336 KB Output is correct
42 Correct 14 ms 23132 KB Output is correct
43 Correct 16 ms 23228 KB Output is correct
44 Correct 182 ms 23260 KB Output is correct
45 Correct 176 ms 23132 KB Output is correct
46 Correct 203 ms 23252 KB Output is correct
47 Correct 12 ms 23132 KB Output is correct
48 Correct 16 ms 23240 KB Output is correct
49 Correct 16 ms 23272 KB Output is correct
50 Correct 193 ms 23132 KB Output is correct
51 Correct 188 ms 23220 KB Output is correct
52 Correct 173 ms 23232 KB Output is correct
53 Correct 169 ms 23220 KB Output is correct
54 Correct 170 ms 23224 KB Output is correct
55 Correct 193 ms 23128 KB Output is correct
56 Correct 4 ms 24924 KB Output is correct
57 Correct 3 ms 23132 KB Output is correct
58 Correct 6 ms 23132 KB Output is correct
59 Correct 2 ms 22876 KB Output is correct
60 Correct 2 ms 24924 KB Output is correct
61 Correct 4 ms 24924 KB Output is correct
62 Execution timed out 5096 ms 32940 KB Time limit exceeded
63 Halted 0 ms 0 KB -