oj.uz

답안 #109631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109631 2019-05-07T08:25:13 Z futurer 동기화 (JOI13_synchronization) C++14
10 / 100
 1974 ms 263168 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)+600000], R[(N<<5)+600000], 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 8 ms 5504 KB Output is correct
2 Correct 8 ms 5580 KB Output is correct
3 Correct 8 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 15 ms 6324 KB Output is correct
7 Correct 128 ms 13728 KB Output is correct
8 Correct 120 ms 11868 KB Output is correct
9 Correct 138 ms 14304 KB Output is correct
10 Correct 1954 ms 56252 KB Output is correct
11 Correct 1928 ms 53408 KB Output is correct
12 Correct 1104 ms 36856 KB Output is correct
13 Runtime error 552 ms 221548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 9 ms 5632 KB Output is correct
4 Correct 10 ms 5760 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 15 ms 5888 KB Output is correct
7 Correct 81 ms 8824 KB Output is correct
8 Correct 1071 ms 36988 KB Output is correct
9 Correct 1129 ms 37108 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1110 ms 36992 KB Output is correct
2 Incorrect 1904 ms 113264 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 10 ms 5632 KB Output is correct
4 Correct 8 ms 5760 KB Output is correct
5 Correct 16 ms 6656 KB Output is correct
6 Correct 143 ms 12656 KB Output is correct
7 Correct 1974 ms 56836 KB Output is correct
8 Correct 1091 ms 37060 KB Output is correct
9 Runtime error 750 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -