oj.uz

Submission #702834

# Submission time Handle Problem Language Result Execution time Memory
702834 2023-02-25T08:34:10 Z hmm789 popa (BOI18_popa) C++14
0 / 100
 21 ms 464 KB 
#include <bits/stdc++.h>
#include "popa.h"
using namespace std;

vector<int> adj[1001];
void dfs(int x, int p, int* lc, int* rc) {
	for(int i : adj[x]) if(i != p) {
		if(lc[x] == -1) lc[x] = i;
		else rc[x] = i;
		dfs(i, x, lc, rc);
	}
}

int solve(int n,int* lc,int* rc) {
	//~ cout << "a" << endl;
	int rt = 0;
	vector<int> par;
	for(int i = 0; i < n; i++) adj[i].clear();
	for(int i = 1; i < n; i++) {
		//~ cout << "a " << i << endl;
		//~ for(int j : par) cout << j << " ";
		//~ cout << endl;
		if(par.size() == 0) {
			if(query(i-1, i, i, i)) {
				adj[i].push_back(i-1);
				adj[i-1].push_back(i);
				rt = i;
			} else {
				adj[i].push_back(i-1);
				adj[i-1].push_back(i);
				par.push_back(i-1);
			}
		} else {
			int l = 0, r = par.size();
			while(l < r) {
				int m = (l+r)/2;
				assert(m < par.size());
				if(query(par[m], i, par[m], par[m])) l = m+1;
				else r = m;
			}
			if(l == 0) {
				adj[i].push_back(par[0]);
				adj[par[0]].push_back(i);
				rt = i;
			}
			while(par.size()>l) par.pop_back();
			while(par.size() && adj[par.back()].size() >= 3) par.pop_back();
			if(l) {
				par.push_back(i);
				adj[i].push_back(par.back());
				adj[par.back()].push_back(i);
			}
		}
	}
	//~ cout << "----" << endl;
	//~ for(int i = 0; i < n; i++) {
		//~ for(int j : adj[i]) cout << j << " ";
		//~ cout << endl;
	//~ }
	for(int i = 0; i < n; i++) lc[i] = rc[i] = -1;
	dfs(rt, -1, lc, rc);
	return rt;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from popa.cpp:1:
popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:37:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     assert(m < par.size());
      |            ~~^~~~~~~~~~~~
popa.cpp:46:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |    while(par.size()>l) par.pop_back();
      |          ~~~~~~~~~~^~

Subtask #1
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 464 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 21 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 384 KB too many queries
2 Halted 0 ms 0 KB -