oj.uz

Submission #1037912

# Submission time Handle Problem Language Result Execution time Memory
1037912 2024-07-29T10:01:55 Z 변재우(#10984) Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 107604 KB 
#include <bits/stdc++.h>
using namespace std;

const int Nmax=100010, sqrtN=600, S=(1<<17), INF=1e9;
int N, M, Q, C[Nmax], p, L[Nmax], R[Nmax], q, I[Nmax], V[2*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];

class DSeg {
public:
    void Init() {
        for(int i=1; i<=q; i++) lx[0][i]=rx[0][i]=D[V[i]], li[0][i]=ri[0][i]=V[i];
        for(int i=1; i<=17; i++) {
            for(int j=1; j<=q; j++) {
                if(j+(1<<(i-1))<=q) {
                    if(lx[i-1][j]<lx[i-1][j+(1<<(i-1))]) lx[i][j]=lx[i-1][j], li[i][j]=li[i-1][j];
                    else lx[i][j]=lx[i-1][j+(1<<(i-1))], li[i][j]=li[i-1][j+(1<<(i-1))];
                }
                if(j-(1<<(i-1))>=1) {
                    if(rx[i-1][j]<rx[i-1][j-(1<<(i-1))]) rx[i][j]=rx[i-1][j], ri[i][j]=ri[i-1][j];
                    else rx[i][j]=rx[i-1][j-(1<<(i-1))], ri[i][j]=ri[i-1][j-(1<<(i-1))];
                }
            }
        }
    }
    int LCA(int a, int b) {
        int l=min(I[a], I[b]), r=max(I[a], I[b]);
        int t=(31-__builtin_clz(r-l+1));
        if(lx[t][l]<rx[t][r]) return li[t][l];
        else return ri[t][r];
    }
private:
    int lx[20][2*Nmax], rx[20][2*Nmax], li[20][2*Nmax], ri[20][2*Nmax];
}QQQ;

inline int LCA(int u, int v) {
    if(u==0 || v==0) return 0;
    return QQQ.LCA(u, v);
}

class Seg {
public:
    Seg() {fill(Mn, Mn+2*S, INF), fill(Mx+1, Mx+2*S, -INF);}
    void Update(int k, int v) {
        Tree[k+=S-1]=v;
        if(v) Mn[k]=Mx[k]=k-S+1;
        else Mn[k]=INF, Mx[k]=-INF;
        for(k>>=1; k; k>>=1) Tree[k]=Tree[k<<1]+Tree[k<<1|1], Mn[k]=min(Mn[k<<1], Mn[k<<1|1]), Mx[k]=max(Mx[k<<1], Mx[k<<1|1]);
    }
    pair<int, int> Query(int l, int r) {
        int mn=INF, mx=-INF;
        for(l+=S-1, r+=S-1; l<r; l>>=1, r>>=1) {
            if(l&1) mn=min(mn, Mn[l]), mx=max(mx, Mx[l]), l++;
            if(!(r&1)) mn=min(mn, Mn[r]), mx=max(mx, Mx[r]), r--;
        }
        if(l==r) mn=min(mn, Mn[l]), mx=max(mx, Mx[l]);
        return {mn, mx};
    }
private:
    int Tree[2*S], Mn[2*S], Mx[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;
    I[curr]=++q, V[q]=curr;
    for(int next:adj[curr]) if(next!=prev) {
        D[next]=D[curr]+1, P[0][next]=curr, DFS(next, curr);
        V[++q]=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;
    int tmp=T.Query(L[x]+1, N).first;
    if(tmp>R[x]) {
        int y=x;
        int rv=tmp, lv=T.Query(1, L[x]-1).second;
        for(int i=16; i>=0; i--) if(P[i][y] && R[P[i][y]]<rv && L[P[i][y]]>lv) 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);
    int tmp=T.Query(L[x]+1, N).first;
    if(tmp>R[x]) {
        int y=x;
        int rv=tmp, lv=T.Query(1, L[x]-1).second;
        for(int i=16; i>=0; i--) if(P[i][y] && R[P[i][y]]<rv && L[P[i][y]]>lv) 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]];
    QQQ.Init();
    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 5 ms 45400 KB Output is correct
2 Correct 5 ms 45404 KB Output is correct
3 Correct 4 ms 47532 KB Output is correct
4 Correct 9 ms 66144 KB Output is correct
5 Correct 9 ms 66160 KB Output is correct
6 Correct 9 ms 66132 KB Output is correct
7 Correct 8 ms 66140 KB Output is correct
8 Correct 8 ms 68184 KB Output is correct
9 Correct 13 ms 68188 KB Output is correct
10 Correct 13 ms 68124 KB Output is correct
11 Correct 12 ms 68116 KB Output is correct
12 Correct 8 ms 68116 KB Output is correct
13 Correct 7 ms 68188 KB Output is correct
14 Correct 7 ms 68136 KB Output is correct
15 Correct 10 ms 68440 KB Output is correct
16 Correct 11 ms 68184 KB Output is correct
17 Correct 11 ms 68348 KB Output is correct
18 Correct 10 ms 68028 KB Output is correct
19 Correct 12 ms 68188 KB Output is correct
20 Correct 12 ms 68184 KB Output is correct
21 Correct 11 ms 68188 KB Output is correct
22 Correct 12 ms 68220 KB Output is correct
23 Correct 14 ms 68188 KB Output is correct
24 Correct 11 ms 68184 KB Output is correct
25 Correct 13 ms 68156 KB Output is correct
26 Correct 10 ms 68188 KB Output is correct
27 Correct 5 ms 37212 KB Output is correct
28 Correct 6 ms 59920 KB Output is correct
29 Correct 7 ms 68188 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 5 ms 45404 KB Output is correct
3 Correct 4 ms 47532 KB Output is correct
4 Correct 9 ms 66144 KB Output is correct
5 Correct 9 ms 66160 KB Output is correct
6 Correct 9 ms 66132 KB Output is correct
7 Correct 8 ms 66140 KB Output is correct
8 Correct 8 ms 68184 KB Output is correct
9 Correct 13 ms 68188 KB Output is correct
10 Correct 13 ms 68124 KB Output is correct
11 Correct 12 ms 68116 KB Output is correct
12 Correct 8 ms 68116 KB Output is correct
13 Correct 7 ms 68188 KB Output is correct
14 Correct 7 ms 68136 KB Output is correct
15 Correct 10 ms 68440 KB Output is correct
16 Correct 11 ms 68184 KB Output is correct
17 Correct 11 ms 68348 KB Output is correct
18 Correct 10 ms 68028 KB Output is correct
19 Correct 12 ms 68188 KB Output is correct
20 Correct 12 ms 68184 KB Output is correct
21 Correct 11 ms 68188 KB Output is correct
22 Correct 12 ms 68220 KB Output is correct
23 Correct 14 ms 68188 KB Output is correct
24 Correct 11 ms 68184 KB Output is correct
25 Correct 13 ms 68156 KB Output is correct
26 Correct 10 ms 68188 KB Output is correct
27 Correct 5 ms 37212 KB Output is correct
28 Correct 6 ms 59920 KB Output is correct
29 Correct 7 ms 68188 KB Output is correct
30 Correct 43 ms 76376 KB Output is correct
31 Correct 49 ms 76492 KB Output is correct
32 Correct 77 ms 76380 KB Output is correct
33 Correct 53 ms 76380 KB Output is correct
34 Correct 54 ms 76540 KB Output is correct
35 Correct 10 ms 76376 KB Output is correct
36 Correct 12 ms 76364 KB Output is correct
37 Correct 10 ms 76380 KB Output is correct
38 Correct 51 ms 76628 KB Output is correct
39 Correct 47 ms 76636 KB Output is correct
40 Correct 46 ms 76652 KB Output is correct
41 Correct 10 ms 76636 KB Output is correct
42 Correct 14 ms 76640 KB Output is correct
43 Correct 12 ms 76636 KB Output is correct
44 Correct 51 ms 76596 KB Output is correct
45 Correct 54 ms 76580 KB Output is correct
46 Correct 51 ms 76592 KB Output is correct
47 Correct 13 ms 76528 KB Output is correct
48 Correct 11 ms 76488 KB Output is correct
49 Correct 11 ms 76380 KB Output is correct
50 Correct 61 ms 76540 KB Output is correct
51 Correct 57 ms 76628 KB Output is correct
52 Correct 55 ms 76376 KB Output is correct
53 Correct 72 ms 76548 KB Output is correct
54 Correct 59 ms 76536 KB Output is correct
55 Correct 63 ms 76380 KB Output is correct
56 Correct 5 ms 39512 KB Output is correct
57 Correct 7 ms 66256 KB Output is correct
58 Correct 9 ms 76380 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 4 ms 37208 KB Output is correct
3 Correct 6 ms 39260 KB Output is correct
4 Correct 3141 ms 103092 KB Output is correct
5 Correct 2615 ms 105300 KB Output is correct
6 Correct 3266 ms 106796 KB Output is correct
7 Execution timed out 5069 ms 107604 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 45404 KB Output is correct
2 Correct 88 ms 97656 KB Output is correct
3 Correct 118 ms 97964 KB Output is correct
4 Correct 102 ms 98168 KB Output is correct
5 Correct 83 ms 99668 KB Output is correct
6 Correct 97 ms 99756 KB Output is correct
7 Correct 141 ms 99668 KB Output is correct
8 Correct 144 ms 99828 KB Output is correct
9 Correct 167 ms 99668 KB Output is correct
10 Correct 189 ms 99920 KB Output is correct
11 Correct 131 ms 99920 KB Output is correct
12 Correct 141 ms 99892 KB Output is correct
13 Correct 156 ms 99924 KB Output is correct
14 Correct 185 ms 99912 KB Output is correct
15 Correct 170 ms 99924 KB Output is correct
16 Correct 153 ms 99812 KB Output is correct
17 Correct 154 ms 99924 KB Output is correct
18 Correct 176 ms 99876 KB Output is correct
19 Correct 78 ms 100084 KB Output is correct
20 Correct 74 ms 99924 KB Output is correct
21 Correct 88 ms 99936 KB Output is correct
22 Correct 121 ms 99928 KB Output is correct
23 Correct 130 ms 99924 KB Output is correct
24 Correct 137 ms 99920 KB Output is correct
25 Correct 156 ms 99780 KB Output is correct
26 Correct 147 ms 99916 KB Output is correct
27 Correct 172 ms 99728 KB Output is correct
28 Correct 146 ms 99900 KB Output is correct
29 Correct 184 ms 99820 KB Output is correct
30 Correct 171 ms 99808 KB Output is correct
31 Correct 171 ms 99944 KB Output is correct
32 Correct 168 ms 99888 KB Output is correct
33 Correct 165 ms 99900 KB Output is correct
34 Correct 177 ms 100012 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45404 KB Output is correct
2 Correct 5 ms 37212 KB Output is correct
3 Correct 5 ms 39472 KB Output is correct
4 Execution timed out 5088 ms 97776 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 5 ms 45404 KB Output is correct
3 Correct 4 ms 47532 KB Output is correct
4 Correct 9 ms 66144 KB Output is correct
5 Correct 9 ms 66160 KB Output is correct
6 Correct 9 ms 66132 KB Output is correct
7 Correct 8 ms 66140 KB Output is correct
8 Correct 8 ms 68184 KB Output is correct
9 Correct 13 ms 68188 KB Output is correct
10 Correct 13 ms 68124 KB Output is correct
11 Correct 12 ms 68116 KB Output is correct
12 Correct 8 ms 68116 KB Output is correct
13 Correct 7 ms 68188 KB Output is correct
14 Correct 7 ms 68136 KB Output is correct
15 Correct 10 ms 68440 KB Output is correct
16 Correct 11 ms 68184 KB Output is correct
17 Correct 11 ms 68348 KB Output is correct
18 Correct 10 ms 68028 KB Output is correct
19 Correct 12 ms 68188 KB Output is correct
20 Correct 12 ms 68184 KB Output is correct
21 Correct 11 ms 68188 KB Output is correct
22 Correct 12 ms 68220 KB Output is correct
23 Correct 14 ms 68188 KB Output is correct
24 Correct 11 ms 68184 KB Output is correct
25 Correct 13 ms 68156 KB Output is correct
26 Correct 10 ms 68188 KB Output is correct
27 Correct 5 ms 37212 KB Output is correct
28 Correct 6 ms 59920 KB Output is correct
29 Correct 7 ms 68188 KB Output is correct
30 Correct 43 ms 76376 KB Output is correct
31 Correct 49 ms 76492 KB Output is correct
32 Correct 77 ms 76380 KB Output is correct
33 Correct 53 ms 76380 KB Output is correct
34 Correct 54 ms 76540 KB Output is correct
35 Correct 10 ms 76376 KB Output is correct
36 Correct 12 ms 76364 KB Output is correct
37 Correct 10 ms 76380 KB Output is correct
38 Correct 51 ms 76628 KB Output is correct
39 Correct 47 ms 76636 KB Output is correct
40 Correct 46 ms 76652 KB Output is correct
41 Correct 10 ms 76636 KB Output is correct
42 Correct 14 ms 76640 KB Output is correct
43 Correct 12 ms 76636 KB Output is correct
44 Correct 51 ms 76596 KB Output is correct
45 Correct 54 ms 76580 KB Output is correct
46 Correct 51 ms 76592 KB Output is correct
47 Correct 13 ms 76528 KB Output is correct
48 Correct 11 ms 76488 KB Output is correct
49 Correct 11 ms 76380 KB Output is correct
50 Correct 61 ms 76540 KB Output is correct
51 Correct 57 ms 76628 KB Output is correct
52 Correct 55 ms 76376 KB Output is correct
53 Correct 72 ms 76548 KB Output is correct
54 Correct 59 ms 76536 KB Output is correct
55 Correct 63 ms 76380 KB Output is correct
56 Correct 5 ms 39512 KB Output is correct
57 Correct 7 ms 66256 KB Output is correct
58 Correct 9 ms 76380 KB Output is correct
59 Correct 5 ms 45400 KB Output is correct
60 Correct 4 ms 37208 KB Output is correct
61 Correct 6 ms 39260 KB Output is correct
62 Correct 3141 ms 103092 KB Output is correct
63 Correct 2615 ms 105300 KB Output is correct
64 Correct 3266 ms 106796 KB Output is correct
65 Execution timed out 5069 ms 107604 KB Time limit exceeded
66 Halted 0 ms 0 KB -