제출 #702830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702830		hmm789	popa (BOI18_popa)	C++14	0 / 100	21 ms	476 KiB

popa

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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();
      |          ~~~~~~~~~~^~

• Subtask 1: 0 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39