oj.uz

답안 #109406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109406 2019-05-06T11:59:04 Z futurer 동기화 (JOI13_synchronization) C++14
30 / 100
 2478 ms 79360 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);
    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 20 ms 19968 KB Output is correct
2 Correct 22 ms 20088 KB Output is correct
3 Correct 23 ms 20096 KB Output is correct
4 Correct 22 ms 19968 KB Output is correct
5 Correct 20 ms 19968 KB Output is correct
6 Correct 26 ms 20096 KB Output is correct
7 Correct 127 ms 22136 KB Output is correct
8 Correct 139 ms 22164 KB Output is correct
9 Correct 133 ms 22164 KB Output is correct
10 Correct 1968 ms 40024 KB Output is correct
11 Correct 1916 ms 39924 KB Output is correct
12 Correct 1620 ms 42488 KB Output is correct
13 Correct 450 ms 45412 KB Output is correct
14 Correct 2478 ms 39916 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1284 ms 71988 KB Output is correct
2 Correct 1112 ms 71408 KB Output is correct
3 Correct 1820 ms 78840 KB Output is correct
4 Correct 1777 ms 79360 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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