oj.uz

Submission #109645

# Submission time Handle Problem Language Result Execution time Memory
109645 2019-05-07T08:54:33 Z futurer Synchronization (JOI13_synchronization) C++14
100 / 100
 2633 ms 93428 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+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*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, 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>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);
        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);
        addfrst(s, e, d, L(id), l, mid);
        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; }
        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);
    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:139: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:142: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:148: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:156: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 9 ms 5504 KB Output is correct
2 Correct 8 ms 5632 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 6 ms 5504 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 16 ms 5632 KB Output is correct
7 Correct 96 ms 8184 KB Output is correct
8 Correct 109 ms 8028 KB Output is correct
9 Correct 104 ms 8056 KB Output is correct
10 Correct 1569 ms 26964 KB Output is correct
11 Correct 1337 ms 27256 KB Output is correct
12 Correct 833 ms 30584 KB Output is correct
13 Correct 563 ms 27500 KB Output is correct
14 Correct 2633 ms 20724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1676 ms 80548 KB Output is correct
2 Correct 1609 ms 79700 KB Output is correct
3 Correct 2499 ms 92656 KB Output is correct
4 Correct 2328 ms 92996 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 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 8 ms 5504 KB Output is correct
6 Correct 13 ms 5760 KB Output is correct
7 Correct 62 ms 8312 KB Output is correct
8 Correct 881 ms 30708 KB Output is correct
9 Correct 865 ms 30832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 30664 KB Output is correct
2 Correct 2397 ms 93036 KB Output is correct
3 Correct 2589 ms 93300 KB Output is correct
4 Correct 2553 ms 93244 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 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 5504 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 103 ms 8056 KB Output is correct
7 Correct 1476 ms 27236 KB Output is correct
8 Correct 817 ms 30620 KB Output is correct
9 Correct 516 ms 27904 KB Output is correct
10 Correct 2517 ms 21512 KB Output is correct
11 Correct 1545 ms 80880 KB Output is correct
12 Correct 1634 ms 80880 KB Output is correct
13 Correct 2313 ms 93428 KB Output is correct