oj.uz

답안 #109632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109632 2019-05-07T08:26:25 Z futurer 동기화 (JOI13_synchronization) C++14
10 / 100
 2215 ms 219468 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+500, M = 2e5+500;
int SZ[N], FRST[N], LST[N], RT[N], DF[M], RTfrst[M], RTlst[M], 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)+200000], R[(N<<5)+200000], 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 7 ms 5632 KB Output is correct
3 Correct 6 ms 5632 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 7 ms 5760 KB Output is correct
6 Correct 14 ms 6272 KB Output is correct
7 Correct 127 ms 13816 KB Output is correct
8 Correct 122 ms 11768 KB Output is correct
9 Correct 107 ms 14328 KB Output is correct
10 Correct 1827 ms 56372 KB Output is correct
11 Correct 1818 ms 53512 KB Output is correct
12 Correct 956 ms 36812 KB Output is correct
13 Incorrect 215 ms 68584 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1333 ms 219468 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 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 12 ms 5888 KB Output is correct
7 Correct 89 ms 8788 KB Output is correct
8 Correct 1100 ms 37168 KB Output is correct
9 Correct 1151 ms 37108 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1046 ms 36980 KB Output is correct
2 Incorrect 2215 ms 118016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5632 KB Output is correct
2 Correct 6 ms 5504 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 7 ms 5760 KB Output is correct
5 Correct 15 ms 6576 KB Output is correct
6 Correct 143 ms 12700 KB Output is correct
7 Correct 1728 ms 56536 KB Output is correct
8 Correct 1079 ms 37116 KB Output is correct
9 Incorrect 350 ms 124268 KB Output isn't correct
10 Halted 0 ms 0 KB -