oj.uz

Submission #109636

# Submission time Handle Problem Language Result Execution time Memory
109636 2019-05-07T08:30:43 Z futurer Synchronization (JOI13_synchronization) C++14
100 / 100
 3704 ms 129976 KB 
// in the name of ALLAH
#pragma GCC optimize("unroll-loops")
#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 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 9 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 14 ms 5760 KB Output is correct
7 Correct 127 ms 8056 KB Output is correct
8 Correct 134 ms 8072 KB Output is correct
9 Correct 138 ms 8056 KB Output is correct
10 Correct 1847 ms 27100 KB Output is correct
11 Correct 1828 ms 27224 KB Output is correct
12 Correct 1104 ms 34316 KB Output is correct
13 Correct 525 ms 27572 KB Output is correct
14 Correct 3301 ms 22652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2273 ms 98800 KB Output is correct
2 Correct 2170 ms 97720 KB Output is correct
3 Correct 3256 ms 126996 KB Output is correct
4 Correct 3013 ms 127664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Correct 7 ms 5528 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 9 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 16 ms 5888 KB Output is correct
7 Correct 100 ms 8752 KB Output is correct
8 Correct 1060 ms 34448 KB Output is correct
9 Correct 1075 ms 34392 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 34420 KB Output is correct
2 Correct 3195 ms 127252 KB Output is correct
3 Correct 3322 ms 129852 KB Output is correct
4 Correct 3704 ms 129856 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 6 ms 5504 KB Output is correct
3 Correct 7 ms 5548 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 14 ms 5632 KB Output is correct
6 Correct 128 ms 8000 KB Output is correct
7 Correct 1796 ms 27220 KB Output is correct
8 Correct 1006 ms 34260 KB Output is correct
9 Correct 579 ms 28028 KB Output is correct
10 Correct 2771 ms 23856 KB Output is correct
11 Correct 1957 ms 101820 KB Output is correct
12 Correct 2220 ms 102084 KB Output is correct
13 Correct 3170 ms 129976 KB Output is correct