oj.uz

답안 #109627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109627 2019-05-07T08:16:56 Z futurer 동기화 (JOI13_synchronization) C++14
10 / 100
 2360 ms 176332 KB 
// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#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 = 2e5+5, M = 2e5+5;
int SZ[N], FRST[N], LST[N], RT[N], DF[M], RTfrst[N], RTlst[N], n, m, q, sz, ptfrst, ptlst;
vector<pii> adj[N], Yals[N];
vector<int> verts;
bitset<N> B;
void ah() { cerr << "!!!\n"; }
struct DS{
    struct node { int mn, mx, lz; } D[M<<3];
    int L[N*40], R[N*40], st = 1;
    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 = 0, int l = 0, int r = m+3){
        if(r-l<2) { D[id]={l, l, -1}; return; }
        int mid = MID(l, r);
        L[id]=st++; R[id]=st++;
        build(L[id], l, mid);
        build(R[id], mid, r);
        merg(id);
        D[id].lz=-1;
    }
    inline void shift(int id){
        int d=D[id].lz;
        if(!(~d)) return;
        L[id]=st++; R[id]=st++;
        D[L[id]] = D[R[id]] = {d, d, d};
        D[id].lz=-1;
    }
    int addlst(int s, int e, int id, int l = 0, int r = m+3){
        if(D[id].mn>e||D[id].mx<s) return(id);
        int nw=st++;
        D[nw].lz=-1;
        if(D[id].mn>=s&&D[id].mx<=e) { D[nw] = {e, e, e}; return(nw); }
        int mid = MID(l, r);
        shift(id);
        L[nw]=L[id]; R[nw]=R[id];
        L[nw]=addlst(s, e, L[nw], l, mid);
        R[nw]=addlst(s, e, R[nw], mid, r);
        merg(nw);
        return(nw);
    }
    int addfrst(int s, int e, int d, int id, int l = 0, int r = m+3){
        if(l>=e || r<=s) return(id);
        int nw=st++;
        D[nw].lz=-1;
        if(l>=s && r<=e) { D[nw]={d, d, d}; return(nw); }
        int mid = MID(l, r);
        shift(id);
        L[nw]=L[id]; R[nw]=R[id];
        L[nw]=addfrst(s, e, d, L[nw], l, mid);
        R[nw]=addfrst(s, e, d, R[nw], mid, r);
        merg(nw);
        return(nw);
    }
    int getLST(int id, int l = 0, int r = m+3){
        if(r-l<2) { if(D[id].mn>=m+2) return(-1); return(l); }
        int mid = MID(l, r);
        shift(id);
        if(D[R[id]].mn<m+2) return(getLST(R[id], mid, r));
        return(getLST(L[id], l, mid));
    }
    int getind(int ind, int id, int l = 0, int r = m+3){
//        cout << id << "!!!\n";
        if(r-l<2) return(D[id].mn);
        int mid = MID(l, r);
        shift(id);
        if(ind<mid) return(getind(ind, L[id], l, mid));
        return(getind(ind, R[id], mid, r));
    }
} 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(RTlst[u]);
    if(!(~LST[u])) return;
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        vector<pii>&v=Yals[x.S];
        if(v.empty()) { RTlst[x.F]=lst.addlst(0, m+2, RTlst[u]); DFSlst(x.F, u); continue; }
        RTlst[x.F]=lst.addlst(0, v[0].F, RTlst[u]);
        for(int i=0;i<(int)v.size()-1;i++) RTlst[x.F]=lst.addlst(v[i].S+1, v[i+1].F, RTlst[x.F]);
        RTlst[x.F]=lst.addlst(v.back().S+1, m+2, RTlst[x.F]);
        DFSlst(x.F, u);
    }
}
void DFSfrst(int u, int p){
    if(FRST[p]>=m+2) return;
    FRST[u]=frst.getind(0, RTfrst[u]);
    if(FRST[u]>=m+2) return;
    for(pii&x:adj[u]) if(x.F^p&&!B[x.F]){
        vector<pii>&v=Yals[x.S];
        if(v.empty()) { RTfrst[x.F]=frst.addfrst(0, m+3, m+2, RTfrst[u]); DFSfrst(x.F, u); continue; }
        RTfrst[x.F]=frst.addfrst(v.back().S+1, m+3, m+2, RTfrst[u]);
        for(int i=(int)v.size()-2;~i;i--){
            int gt=frst.getind(v[i+1].F, RTfrst[x.F]);
            RTfrst[x.F]=frst.addfrst(v[i].S+1, v[i+1].F, gt, RTfrst[x.F]);
        }
        int gt=frst.getind(v[0].F, RTfrst[x.F]);
        RTfrst[x.F]=frst.addfrst(0, v[0].F, gt, RTfrst[x.F]);
        DFSfrst(x.F, u);
    }
}
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;
    RTfrst[u]=0; RTlst[u]=0;
    lst.st=ptlst; frst.st=ptfrst;
    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();
    ptfrst=frst.st; ptlst=lst.st;
    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:151: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:155: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:161: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:169: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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10624 KB Output is correct
2 Correct 11 ms 10624 KB Output is correct
3 Correct 11 ms 10624 KB Output is correct
4 Correct 11 ms 10624 KB Output is correct
5 Correct 14 ms 10624 KB Output is correct
6 Correct 18 ms 11392 KB Output is correct
7 Correct 117 ms 18936 KB Output is correct
8 Correct 137 ms 16940 KB Output is correct
9 Correct 122 ms 19576 KB Output is correct
10 Correct 1855 ms 61504 KB Output is correct
11 Correct 1565 ms 58560 KB Output is correct
12 Correct 1074 ms 42232 KB Output is correct
13 Incorrect 549 ms 154388 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 10624 KB Output is correct
2 Correct 12 ms 10624 KB Output is correct
3 Correct 12 ms 10624 KB Output is correct
4 Correct 15 ms 10624 KB Output is correct
5 Correct 12 ms 10624 KB Output is correct
6 Correct 17 ms 11008 KB Output is correct
7 Correct 73 ms 13816 KB Output is correct
8 Correct 1049 ms 42152 KB Output is correct
9 Correct 1120 ms 42168 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1088 ms 41992 KB Output is correct
2 Incorrect 2360 ms 176332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 10624 KB Output is correct
2 Correct 10 ms 10624 KB Output is correct
3 Correct 12 ms 10624 KB Output is correct
4 Correct 15 ms 10752 KB Output is correct
5 Correct 18 ms 11648 KB Output is correct
6 Correct 125 ms 17720 KB Output is correct
7 Correct 1793 ms 61916 KB Output is correct
8 Correct 950 ms 42028 KB Output is correct
9 Incorrect 502 ms 154988 KB Output isn't correct
10 Halted 0 ms 0 KB -