oj.uz

Submission #300421

# Submission time Handle Problem Language Result Execution time Memory
300421 2020-09-17T07:04:30 Z knon0501 None (KOI18_family) C++14
44 / 100
 2948 ms 191048 KB 
#include <bits/stdc++.h>
using namespace std;
const int MX=5e3+5;
int n,k;
int N1,N2;
vector<int> v[MX];
int lca1[MX][MX];
int lca2[MX][MX];
struct Tree{

vector<int> a[MX];
int dth[MX];
int p[MX][20];
int r;
int lca(int v,int u){
    int i,j;

    if(dth[v]>dth[u])swap(u,v);
    for(i=19 ; i>=0 ; i--)if(dth[u]-dth[v]>=(1<<i))u=p[u][i];
    if(u==v)return v;
    for(i=19 ; i>=0 ; i--){
        if(p[u][i]!=p[v][i]){
            u=p[u][i];
            v=p[v][i];
        }
    }
    return p[v][0];
}
void dfs(int v){
    for(auto u: a[v]){
        if(dth[u])continue;
        p[u][0]=v;
        dth[u]=dth[v]+1;
        dfs(u);
    }
}

void build(){
    dth[r]=1;
    dfs(r);
    for(int i=1 ; i<20 ; i++){
        for(int j=1 ; j<=n ; j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
}

void add(int u,int v){
    a[u].push_back(v);
}
};

Tree T1,T2;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>N1>>N2>>k;
    n=max(N1,N2);
    int i,j;

    for(i=1 ; i<=N1 ; i++){
        int p;
        cin>>p;
        if(p){
            T1.add(p,i);
        }
        else
            T1.r=i;
    }
    for(i=1 ; i<=N2  ; i++){
        int p;
        cin>>p;
        if(p){
            T2.add(p,i);
        }
        else
            T2.r=i;
    }
    T1.build();
    T2.build();

    for(i=1 ; i<=k ; i++){
        for(j=i ; j<=k ; j++){
            lca1[i][j]=lca1[j][i]=T1.dth[T1.lca(i,j)];
            lca2[i][j]=lca2[j][i]=T2.dth[T2.lca(i,j)];
        }
    }
    if(n>=5000)return 0;
    for(i=1 ; i<=k ; i++){
        int mx=0;
        for(j=1 ; j<=n ; j++)
            v[j].clear();
        for(j=1 ; j<=k ; j++){
            v[lca1[i][j]].push_back(j);
        }

        int l=0;

        for(j=1 ; j<=n ; j++){
            for(auto x: v[j-1]){
                mx=max(mx,lca2[i][x]);
                l++;
            }
            for(auto x: v[j]){
            if(mx>lca2[i][x]){
                cout<<"NO";
                return 0;
            }
            }
        }

    }
    cout<<"YES";
    return 0;
}

Compilation message

family.cpp: In member function 'int Tree::lca(int, int)':
family.cpp:16:11: warning: unused variable 'j' [-Wunused-variable]
   16 |     int i,j;
      |           ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 896 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 2 ms 1280 KB Output is correct
16 Correct 1 ms 1024 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 1152 KB Output is correct
19 Correct 2 ms 1664 KB Output is correct
20 Correct 2 ms 1280 KB Output is correct
21 Correct 3 ms 1792 KB Output is correct
22 Correct 1 ms 1024 KB Output is correct
23 Correct 1 ms 768 KB Output is correct
24 Correct 1 ms 896 KB Output is correct
25 Correct 1 ms 768 KB Output is correct
26 Correct 1 ms 1152 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 1 ms 896 KB Output is correct
30 Correct 1 ms 1024 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 896 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 2 ms 1280 KB Output is correct
16 Correct 1 ms 1024 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 1152 KB Output is correct
19 Correct 2 ms 1664 KB Output is correct
20 Correct 2 ms 1280 KB Output is correct
21 Correct 3 ms 1792 KB Output is correct
22 Correct 1 ms 1024 KB Output is correct
23 Correct 1 ms 768 KB Output is correct
24 Correct 1 ms 896 KB Output is correct
25 Correct 1 ms 768 KB Output is correct
26 Correct 1 ms 1152 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 1 ms 896 KB Output is correct
30 Correct 1 ms 1024 KB Output is correct
31 Correct 1 ms 896 KB Output is correct
32 Correct 1 ms 768 KB Output is correct
33 Correct 1 ms 1024 KB Output is correct
34 Correct 1 ms 768 KB Output is correct
35 Correct 1 ms 896 KB Output is correct
36 Correct 4 ms 2048 KB Output is correct
37 Correct 1 ms 1024 KB Output is correct
38 Correct 5 ms 2176 KB Output is correct
39 Correct 3 ms 1664 KB Output is correct
40 Correct 2 ms 1280 KB Output is correct
41 Correct 1 ms 896 KB Output is correct
42 Correct 1 ms 896 KB Output is correct
43 Correct 1 ms 1024 KB Output is correct
44 Correct 1 ms 768 KB Output is correct
45 Correct 1 ms 768 KB Output is correct
46 Correct 3 ms 1792 KB Output is correct
47 Correct 1 ms 1152 KB Output is correct
48 Correct 8 ms 3200 KB Output is correct
49 Correct 1 ms 1152 KB Output is correct
50 Correct 1 ms 896 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 896 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 2 ms 1280 KB Output is correct
16 Correct 1 ms 1024 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 1152 KB Output is correct
19 Correct 2 ms 1664 KB Output is correct
20 Correct 2 ms 1280 KB Output is correct
21 Correct 3 ms 1792 KB Output is correct
22 Correct 1 ms 1024 KB Output is correct
23 Correct 1 ms 768 KB Output is correct
24 Correct 1 ms 896 KB Output is correct
25 Correct 1 ms 768 KB Output is correct
26 Correct 1 ms 1152 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 1 ms 896 KB Output is correct
30 Correct 1 ms 1024 KB Output is correct
31 Correct 1 ms 896 KB Output is correct
32 Correct 1 ms 768 KB Output is correct
33 Correct 1 ms 1024 KB Output is correct
34 Correct 1 ms 768 KB Output is correct
35 Correct 1 ms 896 KB Output is correct
36 Correct 4 ms 2048 KB Output is correct
37 Correct 1 ms 1024 KB Output is correct
38 Correct 5 ms 2176 KB Output is correct
39 Correct 3 ms 1664 KB Output is correct
40 Correct 2 ms 1280 KB Output is correct
41 Correct 1 ms 896 KB Output is correct
42 Correct 1 ms 896 KB Output is correct
43 Correct 1 ms 1024 KB Output is correct
44 Correct 1 ms 768 KB Output is correct
45 Correct 1 ms 768 KB Output is correct
46 Correct 3 ms 1792 KB Output is correct
47 Correct 1 ms 1152 KB Output is correct
48 Correct 8 ms 3200 KB Output is correct
49 Correct 1 ms 1152 KB Output is correct
50 Correct 1 ms 896 KB Output is correct
51 Incorrect 2948 ms 191048 KB Output isn't correct
52 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 896 KB Output is correct
14 Correct 3 ms 1664 KB Output is correct
15 Correct 2 ms 1280 KB Output is correct
16 Correct 1 ms 1024 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 1152 KB Output is correct
19 Correct 2 ms 1664 KB Output is correct
20 Correct 2 ms 1280 KB Output is correct
21 Correct 3 ms 1792 KB Output is correct
22 Correct 1 ms 1024 KB Output is correct
23 Correct 1 ms 768 KB Output is correct
24 Correct 1 ms 896 KB Output is correct
25 Correct 1 ms 768 KB Output is correct
26 Correct 1 ms 1152 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 1 ms 896 KB Output is correct
30 Correct 1 ms 1024 KB Output is correct
31 Correct 1 ms 896 KB Output is correct
32 Correct 1 ms 768 KB Output is correct
33 Correct 1 ms 1024 KB Output is correct
34 Correct 1 ms 768 KB Output is correct
35 Correct 1 ms 896 KB Output is correct
36 Correct 4 ms 2048 KB Output is correct
37 Correct 1 ms 1024 KB Output is correct
38 Correct 5 ms 2176 KB Output is correct
39 Correct 3 ms 1664 KB Output is correct
40 Correct 2 ms 1280 KB Output is correct
41 Correct 1 ms 896 KB Output is correct
42 Correct 1 ms 896 KB Output is correct
43 Correct 1 ms 1024 KB Output is correct
44 Correct 1 ms 768 KB Output is correct
45 Correct 1 ms 768 KB Output is correct
46 Correct 3 ms 1792 KB Output is correct
47 Correct 1 ms 1152 KB Output is correct
48 Correct 8 ms 3200 KB Output is correct
49 Correct 1 ms 1152 KB Output is correct
50 Correct 1 ms 896 KB Output is correct
51 Incorrect 2948 ms 191048 KB Output isn't correct
52 Halted 0 ms 0 KB -