oj.uz

답안 #128610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128610 2019-07-11T07:28:08 Z E869120 Easter Eggs (info1cup17_eastereggs) C++14
86.4 / 100
 22 ms 772 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include "grader.h"
using namespace std;

vector<int> X[1 << 12], G;
bool used[1 << 12]; int N;

void dfs(int pos) {
	used[pos] = true; G.push_back(pos);
	for (int i = 0; i < X[pos].size(); i++) {
		if (used[X[pos][i]] == false) dfs(X[pos][i]);
	}
}

int solve(int cr) {
	cr = min(cr, N);
	vector<int>vec;
	for (int i = 0; i < cr; i++) vec.push_back(G[i]);
	return query(vec);
}

int findEgg(int NN, vector<pair<int, int>> bridges) {
	N = NN;
	for (int i = 0; i < bridges.size(); i++) {
		X[bridges[i].first].push_back(bridges[i].second);
		X[bridges[i].second].push_back(bridges[i].first);
	}
	dfs(1);

	int cx = 0;
	for (int i = 8; i >= 0; i--) {
		int v = solve(cx + (1 << i));
		if (v == 0) cx += (1 << i);
	}
	return G[cx];
}

Compilation message

eastereggs.cpp: In function 'void dfs(int)':
eastereggs.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < bridges.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
26.4 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Number of queries: 9
2 Incorrect 3 ms 424 KB Number of queries: 9
3 Incorrect 4 ms 376 KB Number of queries: 9
4 Incorrect 3 ms 416 KB Number of queries: 9

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 504 KB Number of queries: 9
2 Correct 15 ms 504 KB Number of queries: 9
3 Correct 22 ms 772 KB Number of queries: 9
4 Correct 19 ms 676 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 712 KB Number of queries: 9
2 Correct 15 ms 724 KB Number of queries: 9
3 Correct 18 ms 680 KB Number of queries: 9
4 Correct 20 ms 696 KB Number of queries: 9