oj.uz

답안 #109405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109405 2019-05-06T11:57:35 Z futurer 동기화 (JOI13_synchronization) C++14
30 / 100
 2395 ms 80752 KB 
// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
#define lb(x) (x&(-x))
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(l, r) ((l+r)>>1)
const int N = 2e5+9;
int RT[N], LST[N], FRST[N], AH[N], SZ[N], D[N], DS[N], DSD[N], n, m, q, stk;
vector<pii> adj[N], Yals[N];
vector<int> verts;
bitset<N> B;
set<pii> ST[N];
struct node { int mn, mx, lz; } DSG[N<<3];
struct undo { int id; node nd; } STK[N<<6];
void build(int id = 1, int l = 0, int r = m+3){
    if(r-l<2) { DSG[id]={l, l, -1}; return; }
    int mid = MID(l, r);
    build(L(id), l, mid);
    build(R(id), mid, r);
    DSG[id].mx = max(DSG[L(id)].mx, DSG[R(id)].mx);
    DSG[id].mn = min(DSG[L(id)].mn, DSG[R(id)].mn);
    DSG[id].lz=-1;
}
void shift(int id){
    int d = DSG[id].lz;
    if(!(~d)) return;
    STK[stk++]={L(id), DSG[L(id)]};
    STK[stk++]={R(id), DSG[R(id)]};
    STK[stk++]={id, DSG[id]};
    DSG[L(id)] = DSG[R(id)] = {d, d, d};
    DSG[id].lz=-1;
}
void addsg(int ll, int rr, int id = 1, int l = 0, int r = m+3){
    if(DSG[id].mn>rr) return;
    if(DSG[id].mx<ll) return;
    if(DSG[id].mn>=ll&&DSG[id].mx<=rr){ STK[stk++]={id, DSG[id]}; DSG[id] = {rr, rr, rr}; return; }
    int mid = MID(l, r);
    if(r-l<2) return;
    shift(id);
    addsg(ll, rr, L(id), l, mid);
    addsg(ll, rr, R(id), mid, r);
    STK[stk++]={id, DSG[id]};
    DSG[id].mx = max(DSG[L(id)].mx, DSG[R(id)].mx);
    DSG[id].mn = min(DSG[L(id)].mn, DSG[R(id)].mn);
}
int getind(int id = 1, int l = 0, int r = m+3){
    if(r-l<2) { if(DSG[id].mn>=m+2) return(-1); return(l); }
    int mid = MID(l, r);
    shift(id);
    if(DSG[R(id)].mn<=m+1) return(getind(R(id), mid, r));
    return(getind(L(id), l, mid));
}
void add(int ind, int d) { for(ind++;ind<N;ind+=lb(ind)) D[ind]+=d; }
int  get(int ind){
    int sm=0; for(ind++;ind;ind-=lb(ind)) sm+=D[ind];
    return(sm);
}
int getds(int a) { return(!DS[a]?a:DS[a]=getds(DS[a])); }
void merg(int a, int b, int d){
    a=getds(a); b=getds(b);
    DSD[a]=d;
    if(a^b) DS[b]=a;
}
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, int sz) { for(pii&x:adj[u]) if(x.F^p&&!B[x.F]&&SZ[x.F]>(sz>>1)) return(getrt(x.F, u, sz)); 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 vld(set<pii>&st, int l, int r){
    int frst=-1;
    while(1){
        auto it = st.lower_bound({l, -1});
        if(it==st.end()) break;
        pii x = *it; if(x.F>r) break;
        if(~frst) merg(frst, x.S, r);
        else frst=x.S;
        st.erase(it);
    }
    if(!(~frst)) return;
    merg(frst, frst, r);
    st.insert({r, frst});
}
void DFSg(int u, int p){
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        DFSg(x.F, u);
        if(Yals[x.S].empty()) { vld(ST[x.F], 0, m+2); continue; }
        vld(ST[x.F], 0, Yals[x.S][0].F);
        for(int i=0;i<(int)Yals[x.S].size()-1;i++) vld(ST[x.F], Yals[x.S][i].S+1, Yals[x.S][i+1].F);
        vld(ST[x.F], Yals[x.S].back().S+1, m+2);
    }
    int arshad=0; for(pii&x:adj[u]) if(x.F^p&&!B[x.F]&&SZ[x.F]>=SZ[arshad]) arshad=x.F;
    if(!arshad){
        ST[u].insert({1, u});
        return;
    }
    ST[u].swap(ST[arshad]);
    ST[u].insert({1, u});
    for(pii&x:adj[u]) if(x.F^p&&x.F^arshad&&!B[x.F]) for(pii y:ST[x.F]) ST[u].insert(y);
}
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);
    }
}
void redo(int x) { while(stk>x) { stk--; DSG[STK[stk].id]=STK[stk].nd; } }
void DFS(int u, int p){
    int ind=stk;
    LST[u]=getind();
    redo(ind); // TODO
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        if(Yals[x.S].empty()){
            int ah=stk;
            addsg(0, m+2);
            DFS(x.F, u);
            redo(ah); continue;
        }
        int ah=stk;
        addsg(0, Yals[x.S][0].F);
        for(int i=0;i<(int)Yals[x.S].size()-1;i++) addsg(Yals[x.S][i].F+1, Yals[x.S][i+1].F);
        addsg(Yals[x.S].back().S+1, m+2);
        DFS(x.F, u);
        redo(ah);
    }
}
void darkol(int u){
    setsz(u, 0);
    u=getrt(u, 0, SZ[u]);
    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) { DS[x]=0; DSD[x]=0; while(ST[x].size()) ST[x].erase(ST[x].begin()); }
    DFSg(u, 0);
    for(int&x:verts) FRST[x]=DSD[getds(x)];
    DFS(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+1) RT[u]++;
        if(~LST[x]) RT[x]++;
    }
}
int main(){
    scanf("%d %d %d", &n, &m, &q);
    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;
    }
    LST[0]=0;
    for(int i=1;i<n;i++) if(~LST[i]) Yals[i].push_back({LST[i], m+1});
    build();
    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:159: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:161: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:166: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:175: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

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 19964 KB Output is correct
2 Correct 31 ms 19968 KB Output is correct
3 Correct 25 ms 19968 KB Output is correct
4 Correct 23 ms 20012 KB Output is correct
5 Correct 20 ms 19968 KB Output is correct
6 Correct 32 ms 20224 KB Output is correct
7 Correct 135 ms 22392 KB Output is correct
8 Correct 136 ms 22392 KB Output is correct
9 Correct 138 ms 22392 KB Output is correct
10 Correct 2000 ms 41196 KB Output is correct
11 Correct 2113 ms 41460 KB Output is correct
12 Correct 1718 ms 43860 KB Output is correct
13 Correct 479 ms 46732 KB Output is correct
14 Correct 2395 ms 41152 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1189 ms 73544 KB Output is correct
2 Correct 1254 ms 72756 KB Output is correct
3 Correct 1972 ms 80148 KB Output is correct
4 Correct 1996 ms 80752 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 19968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1775 ms 44112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 19968 KB Output is correct
2 Correct 21 ms 19976 KB Output is correct
3 Correct 22 ms 19968 KB Output is correct
4 Incorrect 22 ms 20096 KB Output isn't correct
5 Halted 0 ms 0 KB -