oj.uz

Submission #109464

# Submission time Handle Problem Language Result Execution time Memory
109464 2019-05-06T16:01:17 Z futurer Synchronization (JOI13_synchronization) C++14
100 / 100
 7781 ms 162148 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 = 2e5+5, M = 2e5+5;
int SZ[N], FRST[N], LST[N], RT[N], DF[N], 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<<2];
    struct undo { int id; node nd; } STK[M*100];
    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(id); ad(L(id)); ad(R(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<N;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){
    int f1=lst.stk;
    LST[u]=lst.getLST();
    lst.redo(f1);
    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);
    }
}
void DFSfrst(int u, int p){
    int f1=frst.stk;
    FRST[u]=frst.getind(0);
    frst.redo(f1);
    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);
    }
}
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);
    sort(verts.begin(), verts.end());
    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});
    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:147: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:150: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:156: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:163: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 11 ms 10624 KB Output is correct
2 Correct 11 ms 10624 KB Output is correct
3 Correct 11 ms 10624 KB Output is correct
4 Correct 11 ms 10624 KB Output is correct
5 Correct 14 ms 10616 KB Output is correct
6 Correct 22 ms 10752 KB Output is correct
7 Correct 235 ms 13180 KB Output is correct
8 Correct 257 ms 13196 KB Output is correct
9 Correct 225 ms 13048 KB Output is correct
10 Correct 3750 ms 32344 KB Output is correct
11 Correct 3938 ms 32076 KB Output is correct
12 Correct 7178 ms 158968 KB Output is correct
13 Correct 527 ms 32532 KB Output is correct
14 Correct 3225 ms 25916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2162 ms 87024 KB Output is correct
2 Correct 2117 ms 86372 KB Output is correct
3 Correct 3501 ms 98672 KB Output is correct
4 Correct 3498 ms 99016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10752 KB Output is correct
2 Correct 15 ms 10624 KB Output is correct
3 Correct 13 ms 10752 KB Output is correct
4 Correct 14 ms 10672 KB Output is correct
5 Correct 12 ms 10624 KB Output is correct
6 Correct 29 ms 11512 KB Output is correct
7 Correct 350 ms 23556 KB Output is correct
8 Correct 7196 ms 161852 KB Output is correct
9 Correct 7781 ms 162148 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7276 ms 159216 KB Output is correct
2 Correct 3285 ms 101168 KB Output is correct
3 Correct 3495 ms 101356 KB Output is correct
4 Correct 3509 ms 101568 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10624 KB Output is correct
2 Correct 11 ms 10624 KB Output is correct
3 Correct 12 ms 10624 KB Output is correct
4 Correct 13 ms 10624 KB Output is correct
5 Correct 27 ms 10880 KB Output is correct
6 Correct 230 ms 13564 KB Output is correct
7 Correct 4113 ms 35280 KB Output is correct
8 Correct 6847 ms 161968 KB Output is correct
9 Correct 624 ms 35604 KB Output is correct
10 Correct 3613 ms 28736 KB Output is correct
11 Correct 2183 ms 90156 KB Output is correct
12 Correct 2093 ms 90216 KB Output is correct
13 Correct 3271 ms 101508 KB Output is correct