답안 #427961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427961 2021-06-15T06:09:20 Z 조영욱(#7659) Corporate life (after hostile takover) (CPSPC17_corpo) C++17
0 / 100
18 ms 22084 KB
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> son1[200000];
vector<int> son2[200000];
int ind1[262144];
int sz1[200000];
int ind2[262144];
int rev2[200000];
int sz2[200000];
int f1=0;
int f2=0;

void dfs1(int v,int prev) {
    ind1[v]=f1++;
    sz1[v]=1;
    for(int nt:son1[v]) {
        dfs1(nt,v);
        sz1[v]+=sz1[nt];
    }
}

void dfs2(int v,int prev) {
    ind2[v]=f2++;
    rev2[ind2[v]]=v;
    sz2[v]=1;
    for(int nt:son2[v]) {
        dfs2(nt,v);
        sz2[v]+=sz2[nt];
    }
}

const int sz=262144;
vector<int> v[sz*2];

void init(int node=1,int nodel=0,int noder=sz-1) {
    if (nodel==noder) {
        if (nodel<n) {
            v[node].push_back(ind1[rev2[nodel]]);
        }
        return;
    }
    int mid=(nodel+noder)/2;
    init(node*2,nodel,mid);
    init(node*2+1,mid+1,noder);
    int i1=0;
    int i2=0;
    while (i1<v[node*2].size()||i2<v[node*2+1].size()) {
        if (i2==v[node*2+1].size()||(i1<v[node*2].size()&&v[node*2][i1]<v[node*2+1][i2])) {
            v[node].push_back(v[node*2][i1++]);
        }
        else {
            v[node].push_back(v[node*2+1][i2++]);
        }
    }
}

int query(int l,int r,int d,int u) {
    int ret=0;
    for(int pl=sz;pl>0;pl/=2) {
        if (l==r) {
            ret+=upper_bound(v[l+pl].begin(),v[l+pl].end(),u)-lower_bound(v[l+pl].begin(),v[l+pl].end(),d);
            //printf("%d ",l+pl);
            break;
        }
        if (l%2==1) {
            ret+=upper_bound(v[l+pl].begin(),v[l+pl].end(),u)-lower_bound(v[l+pl].begin(),v[l+pl].end(),d);
            //printf("%d ",l+pl);
            l++;
        }
        if (r%2==0) {
            ret+=upper_bound(v[r+pl].begin(),v[r+pl].end(),u)-lower_bound(v[r+pl].begin(),v[r+pl].end(),d);
            //printf("%d ",r+pl);
            r--;
        }
        l/=2;
        r/=2;
    }
    //printf("\n");
    return ret;
}

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int p;
        scanf("%d",&p);
        p--;
        son1[p].push_back(i);
    }
    for(int i=1;i<n;i++) {
        int p;
        scanf("%d",&p);
        p--;
        son2[p].push_back(i);
    }
    dfs1(0,-1);
    dfs2(0,-1);
    init();
    for(int i=0;i<n;i++) {
        printf("%d ",query(ind2[i],ind2[i]+sz2[i]-1,ind1[i],ind1[i]+sz1[i]-1)-1);
    }
}

Compilation message

Main.cpp: In function 'void init(int, int, int)':
Main.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (i1<v[node*2].size()||i2<v[node*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
Main.cpp:49:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (i1<v[node*2].size()||i2<v[node*2+1].size()) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if (i2==v[node*2+1].size()||(i1<v[node*2].size()&&v[node*2][i1]<v[node*2+1][i2])) {
      |             ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:50:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if (i2==v[node*2+1].size()||(i1<v[node*2].size()&&v[node*2][i1]<v[node*2+1][i2])) {
      |                                      ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
Main.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 22084 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 22084 KB Output isn't correct
2 Halted 0 ms 0 KB -