oj.uz

Submission #702737

# Submission time Handle Problem Language Result Execution time Memory
702737 2023-02-25T02:02:59 Z jamezzz popa (BOI18_popa) C++17
100 / 100
 93 ms 412 KB 
#include "popa.h"
#include <bits/stdc++.h>
using namespace std;

int par[1005];

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){
		//printf("i=%d:\n",i);
		while(true){
			//printf("cur=%d\n",cur);
			if(query(par[cur]+1,i,par[cur]+1,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];
	return cur;
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 208 KB Output is correct
2 Correct 10 ms 208 KB Output is correct
3 Correct 8 ms 208 KB Output is correct
4 Correct 10 ms 208 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 296 KB Output is correct
2 Correct 92 ms 296 KB Output is correct
3 Correct 50 ms 324 KB Output is correct
4 Correct 87 ms 296 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 308 KB Output is correct
2 Correct 93 ms 412 KB Output is correct
3 Correct 74 ms 320 KB Output is correct
4 Correct 61 ms 296 KB Output is correct