oj.uz

Submission #427950

# Submission time Handle Problem Language Result Execution time Memory
427950 2021-06-15T05:59:31 Z 조영욱(#7659) Corporate life (after hostile takover) (CPSPC17_corpo) C++17
30 / 100
 1000 ms 74452 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 node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return upper_bound(v[node].begin(),v[node].end(),u)-lower_bound(v[node].begin(),v[node].end(),d);
    }
    int mid=(nodel+noder)/2;
    return query(l,r,d,u,node*2,nodel,mid)+query(l,r,d,u,node*2+1,mid+1,noder);
}

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:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
Main.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21964 KB Output is correct
2 Correct 17 ms 21964 KB Output is correct
3 Correct 20 ms 21940 KB Output is correct
4 Correct 19 ms 21984 KB Output is correct
5 Correct 18 ms 22056 KB Output is correct
6 Correct 17 ms 22092 KB Output is correct
7 Correct 20 ms 21964 KB Output is correct
8 Correct 18 ms 22220 KB Output is correct
9 Correct 18 ms 22220 KB Output is correct
10 Correct 19 ms 22268 KB Output is correct
11 Correct 19 ms 22196 KB Output is correct
12 Correct 21 ms 22276 KB Output is correct
13 Correct 18 ms 22220 KB Output is correct
14 Correct 17 ms 22276 KB Output is correct
15 Correct 19 ms 22428 KB Output is correct
16 Correct 20 ms 22468 KB Output is correct
17 Correct 21 ms 22416 KB Output is correct
18 Correct 19 ms 22348 KB Output is correct
19 Correct 20 ms 22476 KB Output is correct
20 Correct 24 ms 22516 KB Output is correct
21 Correct 19 ms 22448 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 21964 KB Output is correct
2 Correct 17 ms 21964 KB Output is correct
3 Correct 20 ms 21940 KB Output is correct
4 Correct 19 ms 21984 KB Output is correct
5 Correct 18 ms 22056 KB Output is correct
6 Correct 17 ms 22092 KB Output is correct
7 Correct 20 ms 21964 KB Output is correct
8 Correct 18 ms 22220 KB Output is correct
9 Correct 18 ms 22220 KB Output is correct
10 Correct 19 ms 22268 KB Output is correct
11 Correct 19 ms 22196 KB Output is correct
12 Correct 21 ms 22276 KB Output is correct
13 Correct 18 ms 22220 KB Output is correct
14 Correct 17 ms 22276 KB Output is correct
15 Correct 19 ms 22428 KB Output is correct
16 Correct 20 ms 22468 KB Output is correct
17 Correct 21 ms 22416 KB Output is correct
18 Correct 19 ms 22348 KB Output is correct
19 Correct 20 ms 22476 KB Output is correct
20 Correct 24 ms 22516 KB Output is correct
21 Correct 19 ms 22448 KB Output is correct
22 Correct 335 ms 42672 KB Output is correct
23 Correct 492 ms 44492 KB Output is correct
24 Correct 448 ms 46768 KB Output is correct
25 Correct 317 ms 42856 KB Output is correct
26 Correct 287 ms 49280 KB Output is correct
27 Correct 306 ms 49360 KB Output is correct
28 Correct 270 ms 49304 KB Output is correct
29 Correct 862 ms 61516 KB Output is correct
30 Correct 906 ms 65184 KB Output is correct
31 Correct 948 ms 69392 KB Output is correct
32 Correct 594 ms 61888 KB Output is correct
33 Correct 581 ms 74384 KB Output is correct
34 Correct 695 ms 74380 KB Output is correct
35 Correct 623 ms 74452 KB Output is correct
36 Correct 963 ms 63188 KB Output is correct
37 Correct 986 ms 67084 KB Output is correct
38 Execution timed out 1067 ms 71604 KB Time limit exceeded
39 Halted 0 ms 0 KB -