Submission #62746

#	Time	Username	Problem	Language	Result	Execution time	Memory
62746		leejseo	족보 (KOI18_family)	C++11	44 / 100	3088 ms	184520 KiB

family

#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 (stderr)

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 / 17
• Subtask 2: 27 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41