oj.uz

Submission #427976

# Submission time Handle Problem Language Result Execution time Memory
427976 2021-06-15T06:32:34 Z 조영욱(#7659) Corporate life (after hostile takover) (CPSPC17_corpo) C++17
100 / 100
 588 ms 56428 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[200001];
int sz2[200000];
int f1=1;
int f2=1;
typedef pair<int,int> P;
typedef pair<P,P> PP;
vector<PP> vec[200001];
int ret[200000];

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;
int seg[sz*2];

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}

void update(int i,int val) {
    i+=sz;
    seg[i]+=val;
    while (i>1) {
        i/=2;
        seg[i]=seg[i*2]+seg[i*2+1];
    }
}

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);
    for(int i=0;i<n;i++) {
        vec[ind2[i]-1].push_back(PP(P(ind1[i],ind1[i]+sz1[i]-1),P(i,-1)));
        vec[ind2[i]+sz2[i]-1].push_back(PP(P(ind1[i],ind1[i]+sz1[i]-1),P(i,1)));
    }
    for(int i=1;i<=n;i++) {
        update(ind1[rev2[i]],1);
        for(int j=0;j<vec[i].size();j++) {
            ret[vec[i][j].second.first]+=vec[i][j].second.second*sum(vec[i][j].first.first,vec[i][j].first.second);
        }
    }
    for(int i=0;i<n;i++) {
        printf("%d ",ret[i]-1);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int j=0;j<vec[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
Main.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~
Main.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Correct 9 ms 14428 KB Output is correct
5 Correct 9 ms 14476 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 10 ms 14540 KB Output is correct
9 Correct 10 ms 14540 KB Output is correct
10 Correct 10 ms 14540 KB Output is correct
11 Correct 10 ms 14540 KB Output is correct
12 Correct 10 ms 14652 KB Output is correct
13 Correct 10 ms 14660 KB Output is correct
14 Correct 13 ms 14540 KB Output is correct
15 Correct 15 ms 14668 KB Output is correct
16 Correct 14 ms 14668 KB Output is correct
17 Correct 11 ms 14796 KB Output is correct
18 Correct 11 ms 14668 KB Output is correct
19 Correct 11 ms 14796 KB Output is correct
20 Correct 12 ms 14796 KB Output is correct
21 Correct 12 ms 14796 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 10 ms 14412 KB Output is correct
4 Correct 9 ms 14428 KB Output is correct
5 Correct 9 ms 14476 KB Output is correct
6 Correct 8 ms 14412 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 10 ms 14540 KB Output is correct
9 Correct 10 ms 14540 KB Output is correct
10 Correct 10 ms 14540 KB Output is correct
11 Correct 10 ms 14540 KB Output is correct
12 Correct 10 ms 14652 KB Output is correct
13 Correct 10 ms 14660 KB Output is correct
14 Correct 13 ms 14540 KB Output is correct
15 Correct 15 ms 14668 KB Output is correct
16 Correct 14 ms 14668 KB Output is correct
17 Correct 11 ms 14796 KB Output is correct
18 Correct 11 ms 14668 KB Output is correct
19 Correct 11 ms 14796 KB Output is correct
20 Correct 12 ms 14796 KB Output is correct
21 Correct 12 ms 14796 KB Output is correct
22 Correct 221 ms 29052 KB Output is correct
23 Correct 270 ms 31052 KB Output is correct
24 Correct 203 ms 33396 KB Output is correct
25 Correct 179 ms 29848 KB Output is correct
26 Correct 197 ms 35264 KB Output is correct
27 Correct 224 ms 35308 KB Output is correct
28 Correct 215 ms 35296 KB Output is correct
29 Correct 472 ms 42436 KB Output is correct
30 Correct 531 ms 46196 KB Output is correct
31 Correct 564 ms 50500 KB Output is correct
32 Correct 434 ms 42332 KB Output is correct
33 Correct 426 ms 54256 KB Output is correct
34 Correct 485 ms 54360 KB Output is correct
35 Correct 481 ms 54188 KB Output is correct
36 Correct 568 ms 43876 KB Output is correct
37 Correct 547 ms 47808 KB Output is correct
38 Correct 588 ms 52444 KB Output is correct
39 Correct 485 ms 43720 KB Output is correct
40 Correct 515 ms 56328 KB Output is correct
41 Correct 518 ms 56400 KB Output is correct
42 Correct 455 ms 56428 KB Output is correct