oj.uz

Submission #64778

# Submission time Handle Problem Language Result Execution time Memory
64778 2018-08-05T15:40:09 Z kjp4155 None (KOI18_family) C++17
0 / 100
 20 ms 14456 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14456 KB Output is correct
2 Incorrect 18 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14456 KB Output is correct
2 Incorrect 18 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14456 KB Output is correct
2 Incorrect 18 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 14456 KB Output is correct
2 Incorrect 18 ms 14456 KB Output isn't correct
3 Halted 0 ms 0 KB -