oj.uz

Submission #1037646

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

const int Nmax=100010, sqrtN=300, 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--];
        }
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33116 KB Output is correct
2 Correct 3 ms 33196 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Incorrect 5 ms 39260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33116 KB Output is correct
2 Correct 3 ms 33196 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Incorrect 5 ms 39260 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33116 KB Output is correct
2 Correct 4 ms 41512 KB Output is correct
3 Correct 9 ms 45648 KB Output is correct
4 Execution timed out 5090 ms 60968 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33112 KB Output is correct
2 Incorrect 209 ms 57424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33116 KB Output is correct
2 Correct 5 ms 41500 KB Output is correct
3 Correct 8 ms 45912 KB Output is correct
4 Execution timed out 5092 ms 58008 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 33116 KB Output is correct
2 Correct 3 ms 33196 KB Output is correct
3 Correct 3 ms 33116 KB Output is correct
4 Incorrect 5 ms 39260 KB Output isn't correct
5 Halted 0 ms 0 KB -