oj.uz

Submission #109638

# Submission time Handle Problem Language Result Execution time Memory
109638 2019-05-07T08:32:05 Z futurer Synchronization (JOI13_synchronization) C++14
100 / 100
 3521 ms 127812 KB 
// in the name of ALLAH
#pragma GCC optimize("O3")
#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+5, M = 2e5+5;
int SZ[N], FRST[N], LST[N], RT[N], DF[M], n, m, q, sz;
vector<pii> adj[N], Yals[N];
vector<int> verts;
bitset<N> B;
struct DS{
    struct node { int mn, mx, lz; } D[M<<3];
    struct undo { int id; node nd; } STK[M*300];
    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, -1}; return; }
        int mid = MID(l, r);
        build(L(id), l, mid);
        build(R(id), mid, r);
        merg(id);
        D[id].lz=-1;
    }
    inline void shift(int id){
        int d=D[id].lz;
        if(!(~d)) return;
        ad(L(id)); ad(R(id)); ad(id);
        D[L(id)] = D[R(id)] = {d, d, d}; D[id].lz=-1;
    }
    void addlst(int s, int e, int id = 1, int l = 0, int r = m+3){
        if(D[id].mn>e||D[id].mx<s) return;
        if(D[id].mn>=s&&D[id].mx<=e) { ad(id); D[id] = {e, e, e}; return; }
        int mid = MID(l, r);
        shift(id);
        addlst(s, e, L(id), l, mid);
        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>=e || r<=s) return;
        if(l>=s && r<=e) { ad(id); D[id]={d, d, d}; return; }
        if(r-l<2) return;
        int mid = MID(l, r);
        shift(id);
        addfrst(s, e, d, L(id), l, mid);
        addfrst(s, e, d, R(id), mid, r);
        ad(id); merg(id);
    }
    int getLST(int id = 1, int l = 0, int r = m+3){
        if(r-l<2) { if(D[id].mn>=m+2) return(-1); return(l); }
        int mid = MID(l, r);
        shift(id);
        if(D[R(id)].mn<m+2) return(getLST(R(id), mid, r));
        return(getLST(L(id), l, mid));
    }
    int getind(int ind, int id = 1, int l = 0, int r = m+3){
        if(r-l<2) return(D[id].mn);
        int mid = MID(l, r);
        shift(id);
        if(ind<mid) return(getind(ind, L(id), l, mid));
        return(getind(ind, 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(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;
    int f1=lst.stk;
    LST[u]=lst.getLST();
    if(!(~LST[u])) { lst.redo(f1); return; }
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        int f2=lst.stk;
        vector<pii>&v=Yals[x.S];
        if(v.empty()) { lst.addlst(0, m+2); DFSlst(x.F, u); lst.redo(f2); continue; }
        lst.addlst(0, v[0].F);
        for(int i=0;i<(int)v.size()-1;i++) lst.addlst(v[i].S+1, v[i+1].F);
        lst.addlst(v.back().S+1, m+2);
        DFSlst(x.F, u);
        lst.redo(f2);
    }
    lst.redo(f1);
}
void DFSfrst(int u, int p){
    if(FRST[p]>=m+2) return;
    int f1=frst.stk;
    FRST[u]=frst.getind(0);
    if(FRST[u]>=m+2) { frst.redo(f1); return; }
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        int f2=frst.stk;
        vector<pii>&v=Yals[x.S];
        if(v.empty()) { frst.addfrst(0, m+3, m+2); DFSfrst(x.F, u); frst.redo(f2); continue; }
        frst.addfrst(v.back().S+1, m+3, m+2);
        for(int i=(int)v.size()-2;~i;i--){
            int gt=frst.getind(v[i+1].F);
            frst.addfrst(v[i].S+1, v[i+1].F, gt);
        }
        int gt=frst.getind(v[0].F);
        frst.addfrst(0, v[0].F, gt);
        DFSfrst(x.F, u);
        frst.redo(f2);
    }
    frst.redo(f1);
}
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;
    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();
    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

synchronization.cpp: In function 'int main()':
synchronization.cpp:152: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:155: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:161: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:169: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5468 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 7 ms 5588 KB Output is correct
6 Correct 14 ms 5632 KB Output is correct
7 Correct 116 ms 8056 KB Output is correct
8 Correct 151 ms 8060 KB Output is correct
9 Correct 130 ms 8056 KB Output is correct
10 Correct 1777 ms 27128 KB Output is correct
11 Correct 1544 ms 26908 KB Output is correct
12 Correct 1096 ms 30640 KB Output is correct
13 Correct 573 ms 27388 KB Output is correct
14 Correct 3121 ms 20816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2203 ms 98840 KB Output is correct
2 Correct 1939 ms 97684 KB Output is correct
3 Correct 3030 ms 127096 KB Output is correct
4 Correct 2905 ms 127448 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5504 KB Output is correct
2 Correct 8 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 9 ms 5612 KB Output is correct
6 Correct 16 ms 5760 KB Output is correct
7 Correct 104 ms 8532 KB Output is correct
8 Correct 1184 ms 30632 KB Output is correct
9 Correct 1144 ms 30660 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1153 ms 30676 KB Output is correct
2 Correct 3396 ms 127232 KB Output is correct
3 Correct 3521 ms 127812 KB Output is correct
4 Correct 2969 ms 127640 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 9 ms 5504 KB Output is correct
5 Correct 13 ms 5760 KB Output is correct
6 Correct 112 ms 8132 KB Output is correct
7 Correct 1911 ms 27296 KB Output is correct
8 Correct 1002 ms 30812 KB Output is correct
9 Correct 483 ms 28072 KB Output is correct
10 Correct 2910 ms 21360 KB Output is correct
11 Correct 2105 ms 99312 KB Output is correct
12 Correct 2121 ms 99312 KB Output is correct
13 Correct 3301 ms 127728 KB Output is correct