oj.uz

답안 #109378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109378 2019-05-06T10:03:34 Z futurer 동기화 (JOI13_synchronization) C++14
30 / 100
 2329 ms 80912 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])); }
pii merg(int a, int b, int d){
    a=getds(a); b=getds(b);
    DSD[a]=d;
    if(a^b) DS[b]=a;
    return(make_pair(d, 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){
    vector<pii> v;
    while(1){
        auto it = st.lower_bound({l, -1});
        if(it==st.end()) break;
        pii x = *it; if(x.F>r) break;
        v.push_back(x); st.erase(it);
    }
    if(v.empty()) return;
    for(pii&x:v) merg(v[0].S, x.S, r);
    st.insert({r, v[0].S});
}
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({0, u});
        return;
    }
    ST[u].swap(ST[arshad]);
    ST[u].insert({0, 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){
    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 aya=stk;
    LST[u]=getind();
    redo(aya);
    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){
    stk=0;
    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; LST[x]=-1; 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) 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 22 ms 19968 KB Output is correct
2 Correct 22 ms 19968 KB Output is correct
3 Correct 21 ms 19964 KB Output is correct
4 Correct 22 ms 19968 KB Output is correct
5 Correct 22 ms 19968 KB Output is correct
6 Correct 29 ms 20224 KB Output is correct
7 Correct 148 ms 22392 KB Output is correct
8 Correct 165 ms 22344 KB Output is correct
9 Correct 189 ms 22308 KB Output is correct
10 Correct 2164 ms 42288 KB Output is correct
11 Correct 2244 ms 42372 KB Output is correct
12 Correct 1839 ms 44872 KB Output is correct
13 Correct 534 ms 47272 KB Output is correct
14 Correct 2329 ms 41560 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1294 ms 74032 KB Output is correct
2 Correct 1216 ms 73456 KB Output is correct
3 Correct 2059 ms 80392 KB Output is correct
4 Correct 2072 ms 80912 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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