oj.uz

Submission #109681

# Submission time Handle Problem Language Result Execution time Memory
109681 2019-05-07T12:27:27 Z futurer Synchronization (JOI13_synchronization) C++14
100 / 100
 2544 ms 91812 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 6 ms 5604 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 6 ms 5504 KB Output is correct
6 Correct 11 ms 5632 KB Output is correct
7 Correct 105 ms 7800 KB Output is correct
8 Correct 80 ms 7784 KB Output is correct
9 Correct 93 ms 7836 KB Output is correct
10 Correct 1478 ms 24872 KB Output is correct
11 Correct 1498 ms 24876 KB Output is correct
12 Correct 779 ms 31220 KB Output is correct
13 Correct 402 ms 24684 KB Output is correct
14 Correct 2532 ms 18628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1536 ms 78236 KB Output is correct
2 Correct 1394 ms 77552 KB Output is correct
3 Correct 2205 ms 91072 KB Output is correct
4 Correct 2169 ms 91636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5632 KB Output is correct
2 Correct 8 ms 5632 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 9 ms 5632 KB Output is correct
5 Correct 7 ms 5504 KB Output is correct
6 Correct 9 ms 5760 KB Output is correct
7 Correct 53 ms 8568 KB Output is correct
8 Correct 719 ms 31176 KB Output is correct
9 Correct 686 ms 31208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 31180 KB Output is correct
2 Correct 2043 ms 91532 KB Output is correct
3 Correct 2125 ms 91812 KB Output is correct
4 Correct 2238 ms 91612 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 12 ms 5676 KB Output is correct
6 Correct 105 ms 7800 KB Output is correct
7 Correct 1398 ms 25208 KB Output is correct
8 Correct 877 ms 31472 KB Output is correct
9 Correct 496 ms 25140 KB Output is correct
10 Correct 2544 ms 19224 KB Output is correct
11 Correct 1484 ms 78960 KB Output is correct
12 Correct 1451 ms 79216 KB Output is correct
13 Correct 2540 ms 91660 KB Output is correct