답안 #403384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403384	2021-05-13T06:26:26 Z	tqbfjotld	족보 (KOI18_family)	C++14	17 / 100	10 ms	14412 KB

family

#include <bits/stdc++.h>
using namespace std;

int n1,n2,k;
vector<int> adjl1[300005];
vector<int> adjl2[300005];
int preord1[300005];
int someval[300005];
int finord[300005];
int cur = 1;
int root1,root2;
int min1[300005];
int max1[300005];
int min2[300005];
int max2[300005];

void dfs1(int node){
    preord1[node] = cur++;
    for (auto x : adjl1[node]){
        dfs1(x);
    }
}

bool cmp(int a, int b){
    return someval[a]<someval[b];
}

void dfs2(int node){
    if (node<=k){
        someval[node] = preord1[node];
        return;
    }
    someval[node] = 999999999;
    for (auto x : adjl2[node]){
        dfs2(x);
        someval[node] = min(someval[node],someval[x]);
    }
    sort(adjl2[node].begin(),adjl2[node].end(),cmp);
}

void dfs3(int node){
    finord[node] = cur++;
    if (node<=k) {
        min2[node] = finord[node];
        max2[node] = finord[node];
    }
    else{
        min2[node] = 999999999;
        max2[node] = -1;
    }
    for (auto x : adjl2[node]){
        dfs3(x);
        min2[node] = min(min2[node],min2[x]);
        max2[node] = max(max2[node],max2[x]);
    }
}

void dfs4(int node){
    if (node<=k) {
        min1[node] = finord[node];
        max1[node] = finord[node];
    }
    else{
        min1[node] = 999999999;
        max1[node] = -1;
    }
    for (auto x : adjl1[node]){
        dfs4(x);
        min1[node] = min(min1[node],min1[x]);
        max1[node] = max(max1[node],max1[x]);
    }
}

bool cmp2(pair<int,int>a,pair<int,int>b){
    if (a.first<b.first) return true;
    if (a.first>b.first) return false;
    return a.second>b.second;
}

int main(){
    scanf("%d%d%d",&n1,&n2,&k);
    for (int x = 1; x<=n1; x++){
        int t;
        scanf("%d",&t);
        if (t!=0){
            adjl1[t].push_back(x);
        }
        else root1 = x;
    }
    for (int x = 1; x<=n2; x++){
        int t;
        scanf("%d",&t);
        if (t!=0){
            adjl2[t].push_back(x);
        }
        else root2 = x;
    }
    dfs1(root1);
    //printf("1\n");
    dfs2(root2);
    //printf("2\n");
    dfs3(root2);
    //printf("3\n");
    dfs4(root1);
    //printf("4\n");
    vector<pair<int,int> > stuff;
    for (int x = k+1; x<=n1; x++){
        stuff.push_back({min1[x],max1[x]});
    }
    for (int x = k+1; x<=n2; x++){
        stuff.push_back({min2[x],max2[x]});
    }
    sort(stuff.begin(),stuff.end(),cmp2);
    stack<int> ends;
    for (auto x : stuff){
        while (!ends.empty() && ends.top()<x.first)ends.pop();
        if (ends.empty() || x.second<=ends.top()){
            ends.push(x.second);
        }
        else{
            printf("NO");
            return 0;
        }
    }
    printf("YES");
}

Compilation message

family.cpp: In function 'int main()':
family.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d%d%d",&n1,&n2,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
family.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
family.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14392 KB	Output is correct
3	Correct	8 ms	14412 KB	Output is correct
4	Correct	8 ms	14388 KB	Output is correct
5	Correct	9 ms	14412 KB	Output is correct
6	Correct	8 ms	14412 KB	Output is correct
7	Correct	9 ms	14388 KB	Output is correct
8	Correct	8 ms	14412 KB	Output is correct
9	Correct	10 ms	14388 KB	Output is correct
10	Correct	9 ms	14392 KB	Output is correct
11	Correct	8 ms	14412 KB	Output is correct
12	Correct	10 ms	14412 KB	Output is correct
13	Correct	10 ms	14412 KB	Output is correct
14	Correct	9 ms	14396 KB	Output is correct
15	Correct	9 ms	14396 KB	Output is correct
16	Correct	9 ms	14360 KB	Output is correct
17	Correct	8 ms	14412 KB	Output is correct
18	Correct	9 ms	14412 KB	Output is correct
19	Correct	9 ms	14412 KB	Output is correct
20	Correct	9 ms	14412 KB	Output is correct
21	Correct	8 ms	14404 KB	Output is correct
22	Correct	8 ms	14388 KB	Output is correct
23	Correct	9 ms	14412 KB	Output is correct
24	Correct	8 ms	14392 KB	Output is correct
25	Correct	8 ms	14392 KB	Output is correct
26	Correct	9 ms	14412 KB	Output is correct
27	Correct	9 ms	14400 KB	Output is correct
28	Correct	8 ms	14376 KB	Output is correct
29	Correct	8 ms	14412 KB	Output is correct
30	Correct	10 ms	14316 KB	Output is correct

Subtask #2
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14392 KB	Output is correct
3	Correct	8 ms	14412 KB	Output is correct
4	Correct	8 ms	14388 KB	Output is correct
5	Correct	9 ms	14412 KB	Output is correct
6	Correct	8 ms	14412 KB	Output is correct
7	Correct	9 ms	14388 KB	Output is correct
8	Correct	8 ms	14412 KB	Output is correct
9	Correct	10 ms	14388 KB	Output is correct
10	Correct	9 ms	14392 KB	Output is correct
11	Correct	8 ms	14412 KB	Output is correct
12	Correct	10 ms	14412 KB	Output is correct
13	Correct	10 ms	14412 KB	Output is correct
14	Correct	9 ms	14396 KB	Output is correct
15	Correct	9 ms	14396 KB	Output is correct
16	Correct	9 ms	14360 KB	Output is correct
17	Correct	8 ms	14412 KB	Output is correct
18	Correct	9 ms	14412 KB	Output is correct
19	Correct	9 ms	14412 KB	Output is correct
20	Correct	9 ms	14412 KB	Output is correct
21	Correct	8 ms	14404 KB	Output is correct
22	Correct	8 ms	14388 KB	Output is correct
23	Correct	9 ms	14412 KB	Output is correct
24	Correct	8 ms	14392 KB	Output is correct
25	Correct	8 ms	14392 KB	Output is correct
26	Correct	9 ms	14412 KB	Output is correct
27	Correct	9 ms	14400 KB	Output is correct
28	Correct	8 ms	14376 KB	Output is correct
29	Correct	8 ms	14412 KB	Output is correct
30	Correct	10 ms	14316 KB	Output is correct
31	Correct	8 ms	14412 KB	Output is correct
32	Correct	9 ms	14412 KB	Output is correct
33	Correct	9 ms	14412 KB	Output is correct
34	Correct	9 ms	14392 KB	Output is correct
35	Correct	9 ms	14376 KB	Output is correct
36	Correct	9 ms	14392 KB	Output is correct
37	Correct	9 ms	14412 KB	Output is correct
38	Correct	9 ms	14412 KB	Output is correct
39	Correct	9 ms	14412 KB	Output is correct
40	Correct	9 ms	14392 KB	Output is correct
41	Correct	10 ms	14388 KB	Output is correct
42	Correct	9 ms	14412 KB	Output is correct
43	Correct	9 ms	14412 KB	Output is correct
44	Incorrect	9 ms	14412 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14392 KB	Output is correct
3	Correct	8 ms	14412 KB	Output is correct
4	Correct	8 ms	14388 KB	Output is correct
5	Correct	9 ms	14412 KB	Output is correct
6	Correct	8 ms	14412 KB	Output is correct
7	Correct	9 ms	14388 KB	Output is correct
8	Correct	8 ms	14412 KB	Output is correct
9	Correct	10 ms	14388 KB	Output is correct
10	Correct	9 ms	14392 KB	Output is correct
11	Correct	8 ms	14412 KB	Output is correct
12	Correct	10 ms	14412 KB	Output is correct
13	Correct	10 ms	14412 KB	Output is correct
14	Correct	9 ms	14396 KB	Output is correct
15	Correct	9 ms	14396 KB	Output is correct
16	Correct	9 ms	14360 KB	Output is correct
17	Correct	8 ms	14412 KB	Output is correct
18	Correct	9 ms	14412 KB	Output is correct
19	Correct	9 ms	14412 KB	Output is correct
20	Correct	9 ms	14412 KB	Output is correct
21	Correct	8 ms	14404 KB	Output is correct
22	Correct	8 ms	14388 KB	Output is correct
23	Correct	9 ms	14412 KB	Output is correct
24	Correct	8 ms	14392 KB	Output is correct
25	Correct	8 ms	14392 KB	Output is correct
26	Correct	9 ms	14412 KB	Output is correct
27	Correct	9 ms	14400 KB	Output is correct
28	Correct	8 ms	14376 KB	Output is correct
29	Correct	8 ms	14412 KB	Output is correct
30	Correct	10 ms	14316 KB	Output is correct
31	Correct	8 ms	14412 KB	Output is correct
32	Correct	9 ms	14412 KB	Output is correct
33	Correct	9 ms	14412 KB	Output is correct
34	Correct	9 ms	14392 KB	Output is correct
35	Correct	9 ms	14376 KB	Output is correct
36	Correct	9 ms	14392 KB	Output is correct
37	Correct	9 ms	14412 KB	Output is correct
38	Correct	9 ms	14412 KB	Output is correct
39	Correct	9 ms	14412 KB	Output is correct
40	Correct	9 ms	14392 KB	Output is correct
41	Correct	10 ms	14388 KB	Output is correct
42	Correct	9 ms	14412 KB	Output is correct
43	Correct	9 ms	14412 KB	Output is correct
44	Incorrect	9 ms	14412 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

Subtask #4
0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14412 KB	Output is correct
2	Correct	8 ms	14392 KB	Output is correct
3	Correct	8 ms	14412 KB	Output is correct
4	Correct	8 ms	14388 KB	Output is correct
5	Correct	9 ms	14412 KB	Output is correct
6	Correct	8 ms	14412 KB	Output is correct
7	Correct	9 ms	14388 KB	Output is correct
8	Correct	8 ms	14412 KB	Output is correct
9	Correct	10 ms	14388 KB	Output is correct
10	Correct	9 ms	14392 KB	Output is correct
11	Correct	8 ms	14412 KB	Output is correct
12	Correct	10 ms	14412 KB	Output is correct
13	Correct	10 ms	14412 KB	Output is correct
14	Correct	9 ms	14396 KB	Output is correct
15	Correct	9 ms	14396 KB	Output is correct
16	Correct	9 ms	14360 KB	Output is correct
17	Correct	8 ms	14412 KB	Output is correct
18	Correct	9 ms	14412 KB	Output is correct
19	Correct	9 ms	14412 KB	Output is correct
20	Correct	9 ms	14412 KB	Output is correct
21	Correct	8 ms	14404 KB	Output is correct
22	Correct	8 ms	14388 KB	Output is correct
23	Correct	9 ms	14412 KB	Output is correct
24	Correct	8 ms	14392 KB	Output is correct
25	Correct	8 ms	14392 KB	Output is correct
26	Correct	9 ms	14412 KB	Output is correct
27	Correct	9 ms	14400 KB	Output is correct
28	Correct	8 ms	14376 KB	Output is correct
29	Correct	8 ms	14412 KB	Output is correct
30	Correct	10 ms	14316 KB	Output is correct
31	Correct	8 ms	14412 KB	Output is correct
32	Correct	9 ms	14412 KB	Output is correct
33	Correct	9 ms	14412 KB	Output is correct
34	Correct	9 ms	14392 KB	Output is correct
35	Correct	9 ms	14376 KB	Output is correct
36	Correct	9 ms	14392 KB	Output is correct
37	Correct	9 ms	14412 KB	Output is correct
38	Correct	9 ms	14412 KB	Output is correct
39	Correct	9 ms	14412 KB	Output is correct
40	Correct	9 ms	14392 KB	Output is correct
41	Correct	10 ms	14388 KB	Output is correct
42	Correct	9 ms	14412 KB	Output is correct
43	Correct	9 ms	14412 KB	Output is correct
44	Incorrect	9 ms	14412 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

답안 #403384

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 27.0

Subtask #3 0 / 15.0

Subtask #4 0 / 41.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 27.0

Subtask #3
0 / 15.0

Subtask #4
0 / 41.0