oj.uz

Submission #1037671

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

const int Nmax=100010, sqrtN=400, 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) {
        Tree[k+=S-1]=v;
        for(k>>=1; k; k>>=1) Tree[k]=Tree[k<<1]+Tree[k<<1|1];
    }
    int Query(int l, int r) {
        int ret=0;
        for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if(l&1) ret+=Tree[l++];
            if(!(r&1)) ret+=Tree[r--];
            if(ret) return ret;
        }
        if(l==r) ret+=Tree[l];
        return ret;
    }
private:
    int Tree[2*S];
}T;

class LSeg {
public:
    void Init() {
        for(int i=1; i<=M; i++) lx[0][i]=rx[0][i]=C[i];
        for(int i=1; i<=16; i++) {
            for(int j=1; j<=M; j++) {
                if(j+(1<<(i-1))<=M) lx[i][j]=LCA(lx[i-1][j], lx[i-1][j+(1<<(i-1))]);
                if(j-(1<<(i-1))>=1) rx[i][j]=LCA(rx[i-1][j], rx[i-1][j-(1<<(i-1))]);
            }
        }
    }
    int Query(int l, int r) {
        int t=(31-__builtin_clz(r-l+1));
        return LCA(lx[t][l], rx[t][r]);
    }
private:
    int lx[20][Nmax], rx[20][Nmax];
}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];
    }
    int np=TL.Query(tl, tr);
    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.Init();
    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;
    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]);
        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;
    }
    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 4 ms 33116 KB Output is correct
2 Correct 3 ms 33116 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Correct 6 ms 39488 KB Output is correct
5 Correct 5 ms 39480 KB Output is correct
6 Correct 5 ms 39336 KB Output is correct
7 Correct 5 ms 39256 KB Output is correct
8 Correct 5 ms 39432 KB Output is correct
9 Correct 7 ms 41308 KB Output is correct
10 Correct 7 ms 41304 KB Output is correct
11 Correct 7 ms 41308 KB Output is correct
12 Correct 5 ms 41472 KB Output is correct
13 Correct 5 ms 41308 KB Output is correct
14 Correct 5 ms 41308 KB Output is correct
15 Correct 6 ms 41548 KB Output is correct
16 Correct 6 ms 41476 KB Output is correct
17 Correct 6 ms 41308 KB Output is correct
18 Correct 7 ms 41308 KB Output is correct
19 Correct 7 ms 41308 KB Output is correct
20 Correct 7 ms 41552 KB Output is correct
21 Correct 7 ms 41308 KB Output is correct
22 Correct 8 ms 41308 KB Output is correct
23 Correct 8 ms 41308 KB Output is correct
24 Correct 7 ms 41308 KB Output is correct
25 Correct 7 ms 41524 KB Output is correct
26 Correct 8 ms 41308 KB Output is correct
27 Correct 5 ms 41308 KB Output is correct
28 Correct 3 ms 26972 KB Output is correct
29 Correct 5 ms 41308 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33116 KB Output is correct
2 Correct 3 ms 33116 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Correct 6 ms 39488 KB Output is correct
5 Correct 5 ms 39480 KB Output is correct
6 Correct 5 ms 39336 KB Output is correct
7 Correct 5 ms 39256 KB Output is correct
8 Correct 5 ms 39432 KB Output is correct
9 Correct 7 ms 41308 KB Output is correct
10 Correct 7 ms 41304 KB Output is correct
11 Correct 7 ms 41308 KB Output is correct
12 Correct 5 ms 41472 KB Output is correct
13 Correct 5 ms 41308 KB Output is correct
14 Correct 5 ms 41308 KB Output is correct
15 Correct 6 ms 41548 KB Output is correct
16 Correct 6 ms 41476 KB Output is correct
17 Correct 6 ms 41308 KB Output is correct
18 Correct 7 ms 41308 KB Output is correct
19 Correct 7 ms 41308 KB Output is correct
20 Correct 7 ms 41552 KB Output is correct
21 Correct 7 ms 41308 KB Output is correct
22 Correct 8 ms 41308 KB Output is correct
23 Correct 8 ms 41308 KB Output is correct
24 Correct 7 ms 41308 KB Output is correct
25 Correct 7 ms 41524 KB Output is correct
26 Correct 8 ms 41308 KB Output is correct
27 Correct 5 ms 41308 KB Output is correct
28 Correct 3 ms 26972 KB Output is correct
29 Correct 5 ms 41308 KB Output is correct
30 Correct 30 ms 45660 KB Output is correct
31 Correct 38 ms 45656 KB Output is correct
32 Correct 44 ms 45756 KB Output is correct
33 Correct 47 ms 45664 KB Output is correct
34 Correct 48 ms 45908 KB Output is correct
35 Correct 10 ms 45660 KB Output is correct
36 Correct 11 ms 45736 KB Output is correct
37 Correct 11 ms 45660 KB Output is correct
38 Correct 39 ms 45660 KB Output is correct
39 Correct 40 ms 45660 KB Output is correct
40 Correct 40 ms 45660 KB Output is correct
41 Correct 11 ms 45656 KB Output is correct
42 Correct 11 ms 45660 KB Output is correct
43 Correct 11 ms 45660 KB Output is correct
44 Correct 41 ms 45792 KB Output is correct
45 Correct 41 ms 45780 KB Output is correct
46 Correct 49 ms 45660 KB Output is correct
47 Correct 11 ms 45656 KB Output is correct
48 Correct 11 ms 45660 KB Output is correct
49 Correct 11 ms 45676 KB Output is correct
50 Correct 40 ms 45660 KB Output is correct
51 Correct 44 ms 45660 KB Output is correct
52 Correct 39 ms 45660 KB Output is correct
53 Correct 45 ms 45660 KB Output is correct
54 Correct 43 ms 45764 KB Output is correct
55 Correct 40 ms 45656 KB Output is correct
56 Correct 10 ms 45912 KB Output is correct
57 Correct 3 ms 27228 KB Output is correct
58 Correct 12 ms 46008 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33112 KB Output is correct
2 Correct 4 ms 41308 KB Output is correct
3 Correct 9 ms 45632 KB Output is correct
4 Correct 4406 ms 61268 KB Output is correct
5 Correct 3178 ms 63868 KB Output is correct
6 Correct 4772 ms 65372 KB Output is correct
7 Execution timed out 5072 ms 68180 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33112 KB Output is correct
2 Correct 227 ms 57564 KB Output is correct
3 Correct 375 ms 57940 KB Output is correct
4 Correct 286 ms 58344 KB Output is correct
5 Correct 395 ms 62540 KB Output is correct
6 Correct 382 ms 62544 KB Output is correct
7 Correct 409 ms 62536 KB Output is correct
8 Correct 412 ms 62548 KB Output is correct
9 Correct 432 ms 62544 KB Output is correct
10 Correct 448 ms 62576 KB Output is correct
11 Correct 436 ms 62372 KB Output is correct
12 Correct 443 ms 62540 KB Output is correct
13 Correct 455 ms 62548 KB Output is correct
14 Correct 439 ms 62540 KB Output is correct
15 Correct 479 ms 62800 KB Output is correct
16 Correct 451 ms 62548 KB Output is correct
17 Correct 417 ms 62604 KB Output is correct
18 Correct 416 ms 62540 KB Output is correct
19 Correct 397 ms 62292 KB Output is correct
20 Correct 397 ms 62060 KB Output is correct
21 Correct 400 ms 61892 KB Output is correct
22 Correct 417 ms 62052 KB Output is correct
23 Correct 421 ms 61900 KB Output is correct
24 Correct 456 ms 62036 KB Output is correct
25 Correct 471 ms 61884 KB Output is correct
26 Correct 503 ms 62080 KB Output is correct
27 Correct 540 ms 62292 KB Output is correct
28 Correct 579 ms 62040 KB Output is correct
29 Correct 605 ms 62120 KB Output is correct
30 Correct 646 ms 62080 KB Output is correct
31 Correct 586 ms 62112 KB Output is correct
32 Correct 602 ms 62096 KB Output is correct
33 Correct 592 ms 62028 KB Output is correct
34 Correct 678 ms 62148 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33116 KB Output is correct
2 Correct 5 ms 41488 KB Output is correct
3 Correct 9 ms 45656 KB Output is correct
4 Execution timed out 5088 ms 57988 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 33116 KB Output is correct
2 Correct 3 ms 33116 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Correct 6 ms 39488 KB Output is correct
5 Correct 5 ms 39480 KB Output is correct
6 Correct 5 ms 39336 KB Output is correct
7 Correct 5 ms 39256 KB Output is correct
8 Correct 5 ms 39432 KB Output is correct
9 Correct 7 ms 41308 KB Output is correct
10 Correct 7 ms 41304 KB Output is correct
11 Correct 7 ms 41308 KB Output is correct
12 Correct 5 ms 41472 KB Output is correct
13 Correct 5 ms 41308 KB Output is correct
14 Correct 5 ms 41308 KB Output is correct
15 Correct 6 ms 41548 KB Output is correct
16 Correct 6 ms 41476 KB Output is correct
17 Correct 6 ms 41308 KB Output is correct
18 Correct 7 ms 41308 KB Output is correct
19 Correct 7 ms 41308 KB Output is correct
20 Correct 7 ms 41552 KB Output is correct
21 Correct 7 ms 41308 KB Output is correct
22 Correct 8 ms 41308 KB Output is correct
23 Correct 8 ms 41308 KB Output is correct
24 Correct 7 ms 41308 KB Output is correct
25 Correct 7 ms 41524 KB Output is correct
26 Correct 8 ms 41308 KB Output is correct
27 Correct 5 ms 41308 KB Output is correct
28 Correct 3 ms 26972 KB Output is correct
29 Correct 5 ms 41308 KB Output is correct
30 Correct 30 ms 45660 KB Output is correct
31 Correct 38 ms 45656 KB Output is correct
32 Correct 44 ms 45756 KB Output is correct
33 Correct 47 ms 45664 KB Output is correct
34 Correct 48 ms 45908 KB Output is correct
35 Correct 10 ms 45660 KB Output is correct
36 Correct 11 ms 45736 KB Output is correct
37 Correct 11 ms 45660 KB Output is correct
38 Correct 39 ms 45660 KB Output is correct
39 Correct 40 ms 45660 KB Output is correct
40 Correct 40 ms 45660 KB Output is correct
41 Correct 11 ms 45656 KB Output is correct
42 Correct 11 ms 45660 KB Output is correct
43 Correct 11 ms 45660 KB Output is correct
44 Correct 41 ms 45792 KB Output is correct
45 Correct 41 ms 45780 KB Output is correct
46 Correct 49 ms 45660 KB Output is correct
47 Correct 11 ms 45656 KB Output is correct
48 Correct 11 ms 45660 KB Output is correct
49 Correct 11 ms 45676 KB Output is correct
50 Correct 40 ms 45660 KB Output is correct
51 Correct 44 ms 45660 KB Output is correct
52 Correct 39 ms 45660 KB Output is correct
53 Correct 45 ms 45660 KB Output is correct
54 Correct 43 ms 45764 KB Output is correct
55 Correct 40 ms 45656 KB Output is correct
56 Correct 10 ms 45912 KB Output is correct
57 Correct 3 ms 27228 KB Output is correct
58 Correct 12 ms 46008 KB Output is correct
59 Correct 3 ms 33112 KB Output is correct
60 Correct 4 ms 41308 KB Output is correct
61 Correct 9 ms 45632 KB Output is correct
62 Correct 4406 ms 61268 KB Output is correct
63 Correct 3178 ms 63868 KB Output is correct
64 Correct 4772 ms 65372 KB Output is correct
65 Execution timed out 5072 ms 68180 KB Time limit exceeded
66 Halted 0 ms 0 KB -