oj.uz

Submission #702734

# Submission time Handle Problem Language Result Execution time Memory
702734 2023-02-25T01:22:40 Z jamezzz popa (BOI18_popa) C++17
0 / 100
 19 ms 424 KB 
#include "popa.h"
#include <bits/stdc++.h>
using namespace std;

int par[1005],lcc[1005],rcc[1005],cnt;
bool vis[1005];

bool check(int u){
	vis[u]=true;
	bool res=true;
	if(lcc[u]!=-1){
		if(vis[lcc[u]])return false;
		//if(arr[lcc[u]]%arr[u]!=0)return false;
		res=res&&check(lcc[u]);
	}
	//check inorder
	if(cnt!=u)return false;
	++cnt;
	if(rcc[u]!=-1){
		if(vis[rcc[u]])return false;
		//if(arr[rcc[u]]%arr[u]!=0)return false;
		res=res&&check(rcc[u]);
	}
	return res;
}

int solve(int n,int* lc,int* rc){
	for(int i=0;i<n;++i)par[i]=-1,lc[i]=-1,rc[i]=-1;
	int cur=0;
	for(int i=1;i<n;++i){
		while(true){
			if(query(0,i,0,cur)){
				if(rc[cur]==-1){
					par[i]=cur;
					rc[cur]=i;
					cur=i;
					break;
				}
				else{
					par[rc[cur]]=i;
					lc[i]=rc[cur];
					rc[cur]=i;
					par[i]=cur;
					cur=i;
					break;
				}
			}
			else{
				if(par[cur]==-1){
					lc[i]=cur;
					par[cur]=i;
					cur=i;
					break;
				}
				else cur=par[cur];
			}
		}
	}
	while(par[cur]!=-1)cur=par[cur];
	
	{
		int root=cur;
		for(int i=0;i<n;++i){
			vis[i]=false;
			lcc[i]=lc[i];
			rcc[i]=rc[i];
		}
		if(root<0||n<=root)assert(false);
		cnt=0;
		bool res=check(root);
		for(int i=0;i<n;++i){
			if(!vis[i])res=false;
		}
		assert(res);
	}
	
	return cur;
}

Subtask #1
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -