oj.uz

답안 #109408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109408 2019-05-06T12:09:19 Z futurer 동기화 (JOI13_synchronization) C++14
30 / 100
 2321 ms 79364 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<<2];
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, -2});
        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-1}); 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});
    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 20096 KB Output is correct
2 Correct 21 ms 20032 KB Output is correct
3 Correct 25 ms 19968 KB Output is correct
4 Correct 25 ms 20060 KB Output is correct
5 Correct 21 ms 19968 KB Output is correct
6 Correct 27 ms 20096 KB Output is correct
7 Correct 118 ms 22168 KB Output is correct
8 Correct 129 ms 22112 KB Output is correct
9 Correct 172 ms 22136 KB Output is correct
10 Correct 2240 ms 39964 KB Output is correct
11 Correct 2321 ms 39944 KB Output is correct
12 Correct 1515 ms 42280 KB Output is correct
13 Correct 406 ms 45276 KB Output is correct
14 Correct 2227 ms 39808 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1291 ms 71652 KB Output is correct
2 Correct 1173 ms 70988 KB Output is correct
3 Correct 1927 ms 79364 KB Output is correct
4 Correct 1948 ms 77868 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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