oj.uz

답안 #109622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109622 2019-05-07T08:12:05 Z futurer 동기화 (JOI13_synchronization) C++14
10 / 100
 2158 ms 216120 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 = 1e5+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<<5)+10000], R[(N<<5)+10000], 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){
        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:150: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:154: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:160: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:168: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 7 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 9 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 14 ms 6272 KB Output is correct
7 Correct 134 ms 13896 KB Output is correct
8 Correct 105 ms 11912 KB Output is correct
9 Correct 125 ms 14548 KB Output is correct
10 Correct 1723 ms 58604 KB Output is correct
11 Correct 1721 ms 55736 KB Output is correct
12 Correct 985 ms 39048 KB Output is correct
13 Incorrect 225 ms 68712 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1353 ms 216120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 7 ms 5632 KB Output is correct
6 Correct 12 ms 5880 KB Output is correct
7 Correct 85 ms 9144 KB Output is correct
8 Correct 986 ms 39796 KB Output is correct
9 Correct 1002 ms 39968 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 993 ms 39940 KB Output is correct
2 Incorrect 2158 ms 110752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 8 ms 5760 KB Output is correct
5 Correct 14 ms 6656 KB Output is correct
6 Correct 107 ms 12920 KB Output is correct
7 Correct 1790 ms 59540 KB Output is correct
8 Correct 1068 ms 39804 KB Output is correct
9 Incorrect 252 ms 69612 KB Output isn't correct
10 Halted 0 ms 0 KB -