oj.uz

Submission #62746

# Submission time Handle Problem Language Result Execution time Memory
62746 2018-07-30T00:28:25 Z leejseo None (KOI18_family) C++11
44 / 100
 3000 ms 184520 KB 
#include <bits/stdc++.h>
using namespace std;

// Make WA AC

typedef vector<int> vi;
typedef vector<vi> vvi;

int N1, N2, K, p1, p2;
vi par1, par2, rk1, rk2;
vvi adj1, adj2;
vvi L1, L2;
bool cutted = false;

void input(){
		scanf("%d%d%d", &N1, &N2, &K);
		par1.resize(N1+1);
		par2.resize(N2+1);
		par1[0] = 0, par2[0] = 0;
		L1.resize(K+1);
		L2.resize(K+1);
		adj1.resize(N1+1);
		adj2.resize(N2+1);
		rk1.resize(N1+1);
		rk2.resize(N2+1);
		for (int i=0; i<=K; i++){
				L1[i].resize(K+1);
				L2[i].resize(K+1);
		}
		for (int i=0; i<=N1; i++) rk1[i] = 0;
		for (int j=0; j<=N2; j++) rk2[j] = 0;
		for (int i=1; i<=N1; i++){
				scanf("%d", &par1[i]);
				adj1[par1[i]].push_back(i);
				if (1 <= par1[i] && par1[i] <= K){
						cutted = true;
						return;
				}
				if (par1[i] == 0){
						if (p1 != 0 || (1 <= i && i <= K)){
								cutted = true;
								return;
						}
						p1 = i;
				}
		}
		for (int i=1; i<=N2; i++){
				scanf("%d", &par2[i]);
				adj2[par2[i]].push_back(i);
				if (1 <= par2[i] && par2[i] <= K){
						cutted = true;
						return;
				}
				if (par2[i] == 0){
						if (p2 != 0 || (1 <= i && i <= K)){
								cutted = true;
								return;
						}
						p2 = i;
				}
		}
		if (p1 == 0 || p2 == 0){
				cutted = true;
				return;
		}
}

void DFS(int i, int par, vvi&adj, vi&rk){
		rk[i] = rk[par] + 1;
		for (auto &v : adj[i]){
				DFS(v, i, adj, rk);
		}		
}

int LCA(int i, int j, vi&par, vi&rk){
		if (rk[j] > rk[i]) swap(i, j);
		//rk[i] >= rk[j]
		while (rk[i] > rk[j]){
				i = par[i];
		}
		while (i != j){
				i = par[i];
				j = par[j];
		}
		return rk[i];
}

void solve(){
		for (int i=1; i<=K; i++){
				for (int j=1; j<=i; j++){
						int l1 = LCA(i, j, par1, rk1);
						int l2 = LCA(i, j, par2, rk2);
						L1[i][j] = l1;
						L1[j][i] = l1;
						L2[i][j] = l2;
						L2[j][i] = l2;
				}
		}
		for (int i=1; i<=K; i++){
				for (int j=1; j<=K; j++){
						for (int k=1; k<j; k++){
								if (L1[i][j] < L1[i][k] && L2[i][k] < L2[i][j]){
										cutted = true;
										return;
								}
								if (L2[i][j] < L2[i][k] && L1[i][k] < L1[i][j]){
										cutted = true;
										return;
								}
						}
				}
		}
}

int main(void){
		input();
		if (cutted){
				printf("NO\n");
				return 0;
		}
		DFS(p1, 0, adj1, rk1);
		DFS(p2, 0, adj2, rk2);
		solve();
		if (cutted){
				printf("NO\n");
				return 0;
		}
		printf("YES\n");
		return 0;
}

Compilation message

family.cpp: In function 'void input()':
family.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &N1, &N2, &K);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &par1[i]);
     ~~~~~^~~~~~~~~~~~~~~~
family.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &par2[i]);
     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 5 ms 788 KB Output is correct
17 Correct 2 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 4 ms 868 KB Output is correct
21 Correct 4 ms 916 KB Output is correct
22 Correct 3 ms 916 KB Output is correct
23 Correct 3 ms 916 KB Output is correct
24 Correct 3 ms 916 KB Output is correct
25 Correct 2 ms 924 KB Output is correct
26 Correct 3 ms 924 KB Output is correct
27 Correct 2 ms 924 KB Output is correct
28 Correct 3 ms 924 KB Output is correct
29 Correct 2 ms 924 KB Output is correct
30 Correct 3 ms 924 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 5 ms 788 KB Output is correct
17 Correct 2 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 4 ms 868 KB Output is correct
21 Correct 4 ms 916 KB Output is correct
22 Correct 3 ms 916 KB Output is correct
23 Correct 3 ms 916 KB Output is correct
24 Correct 3 ms 916 KB Output is correct
25 Correct 2 ms 924 KB Output is correct
26 Correct 3 ms 924 KB Output is correct
27 Correct 2 ms 924 KB Output is correct
28 Correct 3 ms 924 KB Output is correct
29 Correct 2 ms 924 KB Output is correct
30 Correct 3 ms 924 KB Output is correct
31 Correct 3 ms 924 KB Output is correct
32 Correct 3 ms 924 KB Output is correct
33 Correct 3 ms 924 KB Output is correct
34 Correct 3 ms 924 KB Output is correct
35 Correct 3 ms 924 KB Output is correct
36 Correct 7 ms 984 KB Output is correct
37 Correct 3 ms 984 KB Output is correct
38 Correct 8 ms 992 KB Output is correct
39 Correct 6 ms 992 KB Output is correct
40 Correct 4 ms 1004 KB Output is correct
41 Correct 2 ms 1004 KB Output is correct
42 Correct 3 ms 1004 KB Output is correct
43 Correct 4 ms 1004 KB Output is correct
44 Correct 3 ms 1012 KB Output is correct
45 Correct 3 ms 1032 KB Output is correct
46 Correct 4 ms 1032 KB Output is correct
47 Correct 3 ms 1032 KB Output is correct
48 Correct 6 ms 1512 KB Output is correct
49 Correct 3 ms 1512 KB Output is correct
50 Correct 3 ms 1512 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 5 ms 788 KB Output is correct
17 Correct 2 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 4 ms 868 KB Output is correct
21 Correct 4 ms 916 KB Output is correct
22 Correct 3 ms 916 KB Output is correct
23 Correct 3 ms 916 KB Output is correct
24 Correct 3 ms 916 KB Output is correct
25 Correct 2 ms 924 KB Output is correct
26 Correct 3 ms 924 KB Output is correct
27 Correct 2 ms 924 KB Output is correct
28 Correct 3 ms 924 KB Output is correct
29 Correct 2 ms 924 KB Output is correct
30 Correct 3 ms 924 KB Output is correct
31 Correct 3 ms 924 KB Output is correct
32 Correct 3 ms 924 KB Output is correct
33 Correct 3 ms 924 KB Output is correct
34 Correct 3 ms 924 KB Output is correct
35 Correct 3 ms 924 KB Output is correct
36 Correct 7 ms 984 KB Output is correct
37 Correct 3 ms 984 KB Output is correct
38 Correct 8 ms 992 KB Output is correct
39 Correct 6 ms 992 KB Output is correct
40 Correct 4 ms 1004 KB Output is correct
41 Correct 2 ms 1004 KB Output is correct
42 Correct 3 ms 1004 KB Output is correct
43 Correct 4 ms 1004 KB Output is correct
44 Correct 3 ms 1012 KB Output is correct
45 Correct 3 ms 1032 KB Output is correct
46 Correct 4 ms 1032 KB Output is correct
47 Correct 3 ms 1032 KB Output is correct
48 Correct 6 ms 1512 KB Output is correct
49 Correct 3 ms 1512 KB Output is correct
50 Correct 3 ms 1512 KB Output is correct
51 Execution timed out 3088 ms 184520 KB Time limit exceeded
52 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 3 ms 788 KB Output is correct
16 Correct 5 ms 788 KB Output is correct
17 Correct 2 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 4 ms 868 KB Output is correct
21 Correct 4 ms 916 KB Output is correct
22 Correct 3 ms 916 KB Output is correct
23 Correct 3 ms 916 KB Output is correct
24 Correct 3 ms 916 KB Output is correct
25 Correct 2 ms 924 KB Output is correct
26 Correct 3 ms 924 KB Output is correct
27 Correct 2 ms 924 KB Output is correct
28 Correct 3 ms 924 KB Output is correct
29 Correct 2 ms 924 KB Output is correct
30 Correct 3 ms 924 KB Output is correct
31 Correct 3 ms 924 KB Output is correct
32 Correct 3 ms 924 KB Output is correct
33 Correct 3 ms 924 KB Output is correct
34 Correct 3 ms 924 KB Output is correct
35 Correct 3 ms 924 KB Output is correct
36 Correct 7 ms 984 KB Output is correct
37 Correct 3 ms 984 KB Output is correct
38 Correct 8 ms 992 KB Output is correct
39 Correct 6 ms 992 KB Output is correct
40 Correct 4 ms 1004 KB Output is correct
41 Correct 2 ms 1004 KB Output is correct
42 Correct 3 ms 1004 KB Output is correct
43 Correct 4 ms 1004 KB Output is correct
44 Correct 3 ms 1012 KB Output is correct
45 Correct 3 ms 1032 KB Output is correct
46 Correct 4 ms 1032 KB Output is correct
47 Correct 3 ms 1032 KB Output is correct
48 Correct 6 ms 1512 KB Output is correct
49 Correct 3 ms 1512 KB Output is correct
50 Correct 3 ms 1512 KB Output is correct
51 Execution timed out 3088 ms 184520 KB Time limit exceeded
52 Halted 0 ms 0 KB -