#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;
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
popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:45:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
45 | while(par.size()>l) par.pop_back();
| ~~~~~~~~~~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
464 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
320 KB |
too many queries |
| 2 |
Halted |
0 ms |
0 KB |
- |
