Submission #64778

#	Time	Username	Problem	Language	Result	Execution time	Memory
64778		kjp4155	족보 (KOI18_family)	C++17	0 / 100	20 ms	14456 KiB

family

#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int,int> Pi;

int N[2],K;

vector<int> E[2][300500];
int pa[2][300500], root[2];
bool vis[2][300500];

vector<Pi> v[2];

Pi dfs(int k, int x){

	if( 1 <= x && x <= K ) return {x,x};
	int mx = -1, mn = 1e9;
	for(auto e : E[k][x]){
		Pi res = dfs(k, e);
		mx = max(mx, res.second);
		mn = min(mn, res.first);
	}
	v[k].push_back({mn,mx});
	return {mn, mx};
}

int main(){
	scanf("%d%d%d",&N[0],&N[1],&K);
	for(int k=0;k<2;k++){
		for(int i=1;i<=N[k];i++){
			scanf("%d",&pa[k][i]);
			if( pa[k][i] == 0 ) root[k] = i;
		}
	}


	// make tree
	for(int k=0;k<2;k++){
		for(int i=1;i<=K;i++){
			int cur = i;
			while(  !vis[k][cur] && pa[k][cur] != 0 ){
				vis[k][cur] = true;
				E[k][pa[k][cur]].push_back(cur);
				cur = pa[k][cur];
			}
		}	
	}

	dfs(0,root[0]); dfs(1,root[1]);

	// for(auto e : v[0]) printf("%d-%d\n",e.first,e.second);
	// printf("\n");
	// for(auto e : v[0]) printf("%d-%d\n",e.first,e.second);

	for(auto a : v[0]){
		for(auto b : v[1]){

			if( a.second < b.first ) continue;
			if( b.second < a.first ) continue;
			if( a.first <= b.first && b.second <= a.second ) continue;
			if( b.first <= a.first && a.second <= b.second ) continue;
			printf("NO\n");
			return 0;
		}
	}

	printf("YES\n");
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&N[0],&N[1],&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&pa[k][i]);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41