oj.uz

Submission #109673

# Submission time Handle Problem Language Result Execution time Memory
109673 2019-05-07T10:54:27 Z futurer Synchronization (JOI13_synchronization) C++14
100 / 100
 2786 ms 93284 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], 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*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(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();
    if(!(~LST[u])) 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);
    }
}
void DFSfrst(int u, int p){
    if(FRST[p]>=m+2) return;
    FRST[u]=frst.getind(0);
    if(FRST[u]>=m+2) 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; }
        int gt=frst.getind(v[0].F);
        frst.addfrst(0, v[0].F, gt);
        if(!(~frst.getind(0))){
            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);
        }
        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);
    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:141: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:144: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:150: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:158: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 6 ms 5504 KB Output is correct
2 Correct 7 ms 5476 KB Output is correct
3 Correct 6 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 7 ms 5604 KB Output is correct
6 Correct 15 ms 5888 KB Output is correct
7 Correct 93 ms 7996 KB Output is correct
8 Correct 107 ms 8056 KB Output is correct
9 Correct 94 ms 8028 KB Output is correct
10 Correct 1489 ms 27104 KB Output is correct
11 Correct 1247 ms 27120 KB Output is correct
12 Correct 756 ms 32596 KB Output is correct
13 Correct 442 ms 27528 KB Output is correct
14 Correct 2214 ms 20920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1373 ms 80424 KB Output is correct
2 Correct 1354 ms 79600 KB Output is correct
3 Correct 2242 ms 92604 KB Output is correct
4 Correct 2126 ms 93264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 5632 KB Output is correct
5 Correct 7 ms 5632 KB Output is correct
6 Correct 10 ms 5760 KB Output is correct
7 Correct 71 ms 8676 KB Output is correct
8 Correct 881 ms 32860 KB Output is correct
9 Correct 880 ms 32896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 32848 KB Output is correct
2 Correct 2390 ms 93148 KB Output is correct
3 Correct 2236 ms 93280 KB Output is correct
4 Correct 2205 ms 93284 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 6 ms 5504 KB Output is correct
4 Correct 8 ms 5604 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 99 ms 8060 KB Output is correct
7 Correct 1328 ms 27288 KB Output is correct
8 Correct 939 ms 32860 KB Output is correct
9 Correct 482 ms 28016 KB Output is correct
10 Correct 2786 ms 21376 KB Output is correct
11 Correct 1696 ms 81040 KB Output is correct
12 Correct 1502 ms 81040 KB Output is correct
13 Correct 2645 ms 93240 KB Output is correct