Submission #109665

#	Time	Username	Problem	Language	Result	Execution time	Memory
109665		futurer	Synchronization (JOI13_synchronization)	C++14	0 / 100	1260 ms	182984 KiB

synchronization

// in the name of ALLAH
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#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], RTF[N], RTL[N], n, m, q, sz, ptf, ptl;
vector<pii> adj[N], Yals[N];
vector<int> verts;
bitset<N> B;
struct DS{
    struct node { int mn, mx, lz; } D[M<<7];
    int L[N<<7], R[N<<7], st=1;
    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 = 0, int l = 0, int r = m+3){
        if(r-l<2) { D[id]={l, l, 0}; return; }
        int mid = MID(l, r);
        L[id]=st++; R[id]=st++;
        build(L[id], l, mid);
        build(R[id], mid, r);
        merg(id);
        D[id].lz=0;
    }
    int addlst(int s, int e, int id, int l = 0, int r = m+3){
        if(D[id].mn>e||D[id].mx<s) return(id);
        int nw=st++;
        D[nw]=D[id];
        if(D[id].mn>=s&&D[id].mx<=e) {  D[nw] = {e, e, e}; return(nw); }
        int mid = MID(l, r);
        L[nw]=L[id]; R[nw]=R[id];
        L[nw]=addlst(s, e, L[nw], l, mid);
        R[nw]=addlst(s, e, R[nw], mid, r);
        merg(nw);
        return(nw);
    }
    int addfrst(int s, int e, int d, int id, int l = 0, int r = m+3){
        if(l>=e || r<=s) return(id);
        int nw=st++;
        D[nw]=D[id];
        if(l>=s && r<=e) { D[nw]={d, d, d}; return(nw); }
//        if(r-l<2) return(id);
        int mid = MID(l, r);
        L[nw]=L[id]; R[nw]=R[id];
        L[nw]=addfrst(s, e, d, L[nw], l, mid);
        R[nw]=addfrst(s, e, d, R[nw], mid, r);
        merg(nw);
        return(nw);
    }
    int getLST(int id, int tl=0, 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(R[id], tl, mid, r));
        return(getLST(L[id], tl, l, mid));
    }
    int getind(int ind, int id, int tl=0, 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, L[id], tl, l, mid));
        return(getind(ind, R[id], tl, mid, r));
    }
} 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(pii&x:adj[u]) if(x.F^p&&!B[x.F]) { setsz(x.F, u); SZ[u]+=SZ[x.F]; } }
int  getrt(int u, int p) { for(pii&x:adj[u]) if(x.F^p&&!B[x.F]&&SZ[x.F]>=(sz>>1)) return(getrt(x.F, u)); return(u); }
void ini(int u, int p) { verts.push_back(u); for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) ini(x.F, u); }
void DFSlst(int u, int p){
    if(!(~LST[p])) return;
    LST[u]=lst.getLST(RTL[u]);
    if(!(~LST[u])) return;
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        vector<pii>&v=Yals[x.S];
        if(v.empty()) { RTL[x.F]=lst.addlst(0, m+2, RTL[u]); DFSlst(x.F, u); continue; }
        RTL[x.F]=lst.addlst(0, v[0].F, RTL[u]);
        for(int i=0;i<(int)v.size()-1;i++) RTL[x.F]=lst.addlst(v[i].S+1, v[i+1].F, RTL[x.F]);
        RTL[x.F]=lst.addlst(v.back().S+1, m+2, RTL[x.F]);
        DFSlst(x.F, u);
    }
}
void DFSfrst(int u, int p){
    if(FRST[p]>=m+2) return;
    FRST[u]=frst.getind(0, RTF[u]);
    if(FRST[u]>=m+2) return;
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        vector<pii>&v=Yals[x.S];
        if(v.empty()) { RTF[x.F]=frst.addfrst(0, m+3, m+2, RTF[u]); DFSfrst(x.F, u); continue; }
        RTF[x.F]=frst.addfrst(v.back().S+1, m+3, m+2, RTF[u]);
        for(int i=(int)v.size()-2;~i;i--){
            int gt=frst.getind(v[i+1].F, RTF[x.F]);
            RTF[x.F]=frst.addfrst(v[i].S+1, v[i+1].F, gt, RTF[x.F]);
        }
        int gt=frst.getind(v[0].F, RTF[x.F]);
        RTF[x.F]=frst.addfrst(0, v[0].F, gt, RTF[x.F]);
        DFSfrst(x.F, u);
    }
}
void emal(int u, int p, int d){
    if(FRST[u]<m+2){
        add(FRST[u], d);
        for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) emal(x.F, u, d);
    }
}
void Do(int u, int p){
    if(~LST[u]){
        RT[u]+=get(LST[u]);
        for(pii&x:adj[u]) if(x.F^p&&!B[x.F]) Do(x.F, u);
    }
}
inline void darkol(int u){
    setsz(u, 0); sz=SZ[u]; u=getrt(u, 0);
    B[u]=1; for(pii&x:adj[u]) if(!B[x.F]) darkol(x.F); B[u]=0;
    lst.st=ptl; frst.st=ptf;
    RTL[u]=RTF[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 t=0;t<2;t++){
        for(pii&x:adj[u]) if(!B[x.F]){
            Do(x.F, u);
            emal(x.F, u, 1);
        }
        for(pii&x:adj[u]) if(!B[x.F]) emal(x.F, u, -1);
        reverse(adj[u].begin(), adj[u].end());
    }
    for(int&x:verts) if(x^u){
        if(FRST[x]<m+2) RT[u]++;
        if(~LST[x]) RT[x]++;
    }
}
int main(){
    scanf("%d %d %d", &n, &m, &q);
    frst.build(); lst.build();
    ptf=frst.st; ptl=lst.st;
    for(int i=1;i<n;i++){
        int a, b; scanf("%d %d", &a, &b);
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    memset(LST, -1, sizeof(LST));
    for(int i=1;i<=m;i++){
        int a; scanf("%d", &a);
        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; scanf("%d", &a);
        printf("%d\n", RT[a]+1);
    }
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:146:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:152:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a; scanf("%d", &a);
                ~~~~~^~~~~~~~~~
synchronization.cpp:160:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a; scanf("%d", &a);
                ~~~~~^~~~~~~~~~

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