oj.uz

Submission #67633

# Submission time Handle Problem Language Result Execution time Memory
67633 2018-08-15T07:11:24 Z cdemirer Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 42 ms 564 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

#include "grader.h"

bool poss[512];
vvi edges;
vi queryVector;

int parent[512];
int expand(int x, int rem) {
	queryVector.pb(x);
	if (poss[x]) {
		rem -= 1;
	}
	for (int i = 0; i < edges[x].size(); i++) {
		if (!rem) break;
		int y = edges[x][i];
		if (y == parent[x]) continue;
		parent[y] = x;
		rem = expand(y, rem);
	}
	return rem;
}

int findEgg (int N, vii bridges) {
	for (int i = 0; i < 512; i++) poss[i] = true;
	edges.clear();
	edges.resize(N);
	for (int i = 0; i < bridges.size(); i++) {
		edges[ bridges[i].first-1 ].pb(bridges[i].second-1);
		edges[ bridges[i].second-1 ].pb(bridges[i].first-1);
	}
	while (true) {
		//cerr << "currently possible: ";
		//for (int i = 0; i < N; i++) if (poss[i]) cerr << i << " ";
		//cerr << endl;
		
		queryVector.clear();
		int cnt = 0; for (int i = 0; i < N; i++) cnt += poss[i];
		int st = 0; for (int i = 0; i < N; i++) if (poss[i]) st = i;
		
		parent[st] = -1;
		expand(st, cnt/2);
		
		//cerr << "querying: ";
		//for (int i = 0; i < queryVector.size(); i++) cerr << queryVector[i] << " ";
		//cerr << endl;
		vi _qv(queryVector.size());
		for (int i = 0; i < queryVector.size(); i++) _qv[i] = queryVector[i]+1;
		int res = query(_qv);
		if (res) {
			vi ok;
			for (int i = 0; i < queryVector.size(); i++) if (poss[queryVector[i]]) ok.pb(queryVector[i]);
			for (int i = 0; i < 512; i++) poss[i] = false;
			for (int i = 0; i < ok.size(); i++) poss[ok[i]] = true;
		} else {
			for (int i = 0; i < queryVector.size(); i++) poss[queryVector[i]] = false;
		}
		
		//cerr << "now possible: ";
		//for (int i = 0; i < N; i++) if (poss[i]) cerr << i << " ";
		//cerr << endl;
		//cerr << endl;
		
		cnt = 0; for (int i = 0; i < N; i++) cnt += poss[i];
		if (cnt == 1) break;
	}
	for (int i = 0; i < N; i++) if (poss[i]) return i+1;
	exit(-1);
}

Compilation message

eastereggs.cpp: In function 'int expand(int, int)':
eastereggs.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, vii)':
eastereggs.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < bridges.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~
eastereggs.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < queryVector.size(); i++) _qv[i] = queryVector[i]+1;
                   ~~^~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < queryVector.size(); i++) if (poss[queryVector[i]]) ok.pb(queryVector[i]);
                    ~~^~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < ok.size(); i++) poss[ok[i]] = true;
                    ~~^~~~~~~~~~~
eastereggs.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < queryVector.size(); i++) poss[queryVector[i]] = false;
                    ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Number of queries: 4
2 Correct 3 ms 376 KB Number of queries: 4
3 Correct 4 ms 516 KB Number of queries: 4
4 Correct 2 ms 516 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 516 KB Number of queries: 8
2 Correct 21 ms 516 KB Number of queries: 9
3 Correct 22 ms 544 KB Number of queries: 9
4 Correct 35 ms 544 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 564 KB Number of queries: 9
2 Correct 28 ms 564 KB Number of queries: 9
3 Correct 32 ms 564 KB Number of queries: 9
4 Correct 42 ms 564 KB Number of queries: 9