Submission #109681

#	Time	Username	Problem	Language	Result	Execution time	Memory
109681		futurer	Synchronization (JOI13_synchronization)	C++14	100 / 100	2544 ms	91812 KiB

synchronization

// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(l, r) ((l+r)>>1)
#define lb(x) (x&(-x))
#define pii pair<int, int>
#define F first
#define S second
const int N = 1e5+500, M = 2e5+500;
int SZ[N], FRST[N], LST[N], RT[N], DF[M], HD[M], TL[M], NXT[M], A[M], BB[M], V[M], nxt, n, m, q, sz;
int gt(int a, int x) { return(A[x]^BB[x]^a); }
void aded(int a, int x){
    if(~TL[a]) { NXT[TL[a]]=nxt; V[nxt]=x; TL[a]=nxt++; }
    else { TL[a]=HD[a]=nxt; V[nxt++]=x; }
}
vector<pii> Yals[N];
vector<int> verts;
bitset<N> B;
void ah() { cerr << "!!!\n"; }
inline int	read()
{
    int x = 0;
    char ch = getchar();
    bool positive = 1;
    for (; ch < '0' || ch > '9'; ch = getchar())	if (ch == '-')  positive = 0;
    for (; ch >= '0' && ch <= '9'; ch = getchar())	x = x * 10 + ch - '0';
    return positive ? x : -x;
}
struct DS{
    struct node { int mn, mx, lz; } D[M<<3];
    struct undo { int id; node nd; } STK[M*313];
    int stk=0;
    inline void ad(int id) { STK[stk++]={id, D[id]}; }
    inline void merg(int id) { D[id].mx=max(D[L(id)].mx, D[R(id)].mx); D[id].mn=min(D[L(id)].mn, D[R(id)].mn); }
    void build(int id = 1, int l = 0, int r = m+3){
        if(r-l<2) { D[id]={l, l, 0}; return; }
        int mid = MID(l, r);
        build(L(id), l, mid);
        build(R(id), mid, r);
        merg(id);
    }
    void addlst(int s, int e, int id = 1, int l = 0, int r = m+3){
        if(D[id].mn>=s&&D[id].mx<=e) { ad(id); D[id] = {e, e, e}; return; }
        int mid = MID(l, r);
        if(!(D[L(id)].mn>e||D[L(id)].mx<s)) addlst(s, e, L(id), l, mid);
        if(!(D[R(id)].mn>e||D[R(id)].mx<s)) addlst(s, e, R(id), mid, r);
        ad(id); merg(id);
    }
    void addfrst(int s, int e, int d, int id = 1, int l = 0, int r = m+3){
        if(l>=s && r<=e) { ad(id); D[id]={d, d, d}; return; }
        if(r-l<2) return;
        int mid = MID(l, r);
        if(!(s>=mid)) addfrst(s, e, d, L(id), l, mid);
        if(!(mid>=e)) addfrst(s, e, d, R(id), mid, r);
        ad(id); merg(id);
    }
    int getLST(int tl=0, int id = 1, int l = 0, int r = m+3){
        tl=max(tl, D[id].lz);
        if(r-l<2) { if(max(tl, D[id].mn)>=m+2) return(-1); return(l); }
        int mid = MID(l, r);
        if(max(tl, D[R(id)].mn)<m+2) return(getLST(tl, R(id), mid, r));
        return(getLST(tl, L(id), l, mid));
    }
    int getind(int ind, int tl=0, int id = 1, int l = 0, int r = m+3){
        tl=max(tl, D[id].lz);
        if(r-l<2) return(max(tl, D[id].mn));
        int mid = MID(l, r);
        if(ind<mid) return(getind(ind, tl, L(id), l, mid));
        return(getind(ind, tl, R(id), mid, r));
    }
    inline void redo(int x) { while(stk>x) { stk--; D[STK[stk].id]=STK[stk].nd; } }
} frst, lst;
inline void add(int ind, int d) { for(ind++;ind<M;ind+=lb(ind)) DF[ind]+=d; }
inline int  get(int ind){
    int sm=0; for(ind++;ind;ind-=lb(ind)) sm+=DF[ind];
    return(sm);
}
void setsz(int u, int p){
    SZ[u]=1;
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(x^p&&!B[x]) { setsz(x, u); SZ[u]+=SZ[x]; }
    }
}
int  getrt(int u, int p){
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(x^p&&!B[x]&&SZ[x]>(sz>>1)) return(getrt(x, u));
    }
    return(u);
}
void ini(int u, int p){
    verts.push_back(u);
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(x^p&&!B[x]) ini(x, u);
    }
}
void DFSlst(int u, int p){
    if(!(~LST[p])) return;
    LST[u]=lst.getLST();
    if(!(~LST[u])) return;
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(x^p&&!B[x]){
            int f2=lst.stk;
            vector<pii>&v=Yals[V[i]];
            if(v.empty()) { lst.addlst(0, m+2); DFSlst(x, u); lst.redo(f2); continue; }
            lst.addlst(0, v[0].F);
            for(int j=0;j<(int)v.size()-1;j++) lst.addlst(v[j].S+1, v[j+1].F);
            lst.addlst(v.back().S+1, m+2);
            DFSlst(x, u);
            lst.redo(f2);
        }
    }
}
void DFSfrst(int u, int p){
    if(FRST[p]>=m+2) return;
    FRST[u]=frst.getind(0);
    if(FRST[u]>=m+2) return;
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(x^p&&!B[x]){
            int f2=frst.stk;
            vector<pii>&v=Yals[V[i]];
            if(v.empty()) { frst.addfrst(0, m+3, m+2); DFSfrst(x, u); frst.redo(f2); continue; }
            int ind=frst.getind(v[0].F);
            frst.addfrst(0, v[0].F, ind);
            if(!(~frst.getind(0))){
                DFSfrst(x, u);
                frst.redo(f2);
                continue;
            }
            frst.addfrst(v.back().S+1, m+3, m+2);
            for(int j=(int)v.size()-2;~j;j--){
                int ind=frst.getind(v[j+1].F);
                frst.addfrst(v[j].S+1, v[j+1].F, ind);
            }
            DFSfrst(x, u);
            frst.redo(f2);
        }
    }
}
void emal(int u, int p, int d){
    if(FRST[u]<m+2){
        add(FRST[u], d);
        for(int i=HD[u];~i;i=NXT[i]){
            int x=gt(u, V[i]);
            if(x^p&&!B[x]) emal(x, u, d);
        }
    }
}
void Do(int u, int p, int d){
    if(~LST[u]){
        RT[u]+=get(LST[u])*d;
        for(int i=HD[u];~i;i=NXT[i]){
            int x=gt(u, V[i]);
            if(x^p&&!B[x]) Do(x, u, d);
        }
    }
}
inline void darkol(int u){
    setsz(u, 0); sz=SZ[u]; u=getrt(u, 0);
    B[u]=1; for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(!B[x]) darkol(x);
    }
    B[u]=0;
    while(verts.size()) verts.pop_back();
    ini(u, 0);
    for(int&x:verts) { FRST[x]=m+2; LST[x]=-1; }
    DFSlst(u, 0);
    DFSfrst(u, 0);
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(!B[x]) emal(x, u, 1);
    }
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(!B[x]) Do(x, u, 1);
    }
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(!B[x]) emal(x, u, -1);
    }
    for(int i=HD[u];~i;i=NXT[i]){
        int x=gt(u, V[i]);
        if(!B[x]){
            emal(x, u, 1);
            Do(x, u, -1);
            emal(x, u, -1);
        }
    }
    for(int&x:verts) if(x^u){
        if(FRST[x]<m+2) RT[u]++;
        if(~LST[x]) RT[x]++;
    }
}
int main(){
    memset(HD, -1, sizeof(HD)); memset(TL, -1, sizeof(TL)); memset(NXT, -1, sizeof(NXT));
    n = read(); m = read(); q = read();
    frst.build(); lst.build();
    for(int i=1;i<n;i++){
        A[i] = read(); BB[i] = read();
        aded(A[i], i); aded(BB[i], i);
    }
    memset(LST, -1, sizeof(LST));
    for(int i=1;i<=m;i++){
        int a; a = read();
        if(~LST[a]) { Yals[a].push_back({LST[a], i}); LST[a]=-1; }
        else LST[a]=i;
    }
    for(int i=1;i<n;i++) if(~LST[i]) Yals[i].push_back({LST[i], m+1});
    LST[0]=0;
    darkol(1);
    for(int Q=0;Q<q;Q++){
        int a; a = read();
        printf("%d\n", RT[a]+1);
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40