Submission #67651

#	Time	Username	Problem	Language	Result	Execution time	Memory
67651		ekrem	Easter Eggs (info1cup17_eastereggs)	C++11	100 / 100	44 ms	608 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define MAXN 550
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;



static int N, X, cntQ;
static vector < int > v[1009];


typedef pair < int , int > ii;
typedef vector < int > vi;

// int query (vector < int > h)
// {
//     cntQ ++;
//     int ap[1009];
//     if (h.empty ()) return 0;
//     for (int i=1; i<=N; i++)
//         ap[i] = 0;
//     for (vi::iterator it = h.begin (); it != h.end (); it ++)
//         ap[*it] = 1;
//     queue < int > cc;
//     cc.push (h[0]), ap[h[0]] = 2;
//     while (!cc.empty ())
//     {
//         int nod = cc.front ();
//         cc.pop ();
//         for (vi::iterator it = v[nod].begin (); it != v[nod].end (); it ++)
//             if (ap[*it] == 1)
//                 ap[*it] = 2, cc.push (*it);
//     }
//     for (int i=1; i<=N; i++)
//         if (ap[i] == 1) return -1;
//     for (vi::iterator it = h.begin (); it != h.end (); it ++)
//         if (*it == X) return 1;
//     return 0;
// }





int n = -1, ans, u[MAXN], h[MAXN], say;
vi g[MAXN], sor;

void dfs(int node, int par, int kac){
	if(say >= kac)
		return;
	sor.pb(node);
	if(u[node])
		say++;
	if(say >= kac)
		return;
	for(int i = 0; i < g[node].size(); i++)
		if(g[node][i] != par)
			dfs(g[node][i], node, kac);
}

void bul(int node, int kac){
	if(kac == 1){
		for(int i = 1; i <= n; i++)
			if(u[i]){
				ans = i;
				return;
			}
	}
	sor.clear();
	say = 0;
	dfs(node, 0, kac/2);
	// for(int i = 0; i < sor.size(); i++)cout << sor[i] << " ";cout << endl;
	if(query(sor)){
		if(sor.size() == 1){
			ans = sor[0];
			return;
		}
		memset(h, 0, sizeof h);
		for(int i = 0; i < sor.size(); i++)
			h[sor[i]] = 1;
		for(int i = 1; i <= n; i++)
			if(!h[i])
				u[i] = 0;
		bul(node, kac/2);
	}else{
		for(int i = 0; i < sor.size(); i++)
			u[sor[i]] = 0;
		bul(node, kac - kac/2);
	}
}

int findEgg (int N, vector < ii > b){

	for(int i = 1; i <= N; i++)
		u[i] = 1;


	if(n == -1)
		for(int i = 0; i < b.size(); i++){
			g[b[i].st].pb(b[i].nd);
			g[b[i].nd].pb(b[i].st);
		}

	ans = -1;
	n = N;

	bul(1, n);

	return ans;
}



// int main ()
// {
// freopen ("in.txt", "r", stdin);
// freopen ("out.txt", "w", stdout);

// scanf ("%d", &N);
// int Queries;
// vector < pair < int, int > > param;
// for (int i=1; i<N; i++)
// {
//     int x, y;
//     scanf ("%d %d", &x, &y);
//     v[x].push_back (y);
//     v[y].push_back (x);
//     param.push_back (mp(x, y) );
// }
// scanf ("%d", &Queries);
// while (Queries --)
// {
//     scanf ("%d", &X), cntQ = 0;
//     int Y = findEgg (N, param);
//     if (X != Y)
//     {
//         printf ("WA %d instead of %d\n", Y, X);
//         return 0;
//     }
//     printf ("OK %d\n", cntQ);
// }
// return 0;
// }

Compilation message (stderr)

eastereggs.cpp: In function 'void dfs(int, int, int)':
eastereggs.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'void bul(int, int)':
eastereggs.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sor.size(); i++)
                  ~~^~~~~~~~~~~~
eastereggs.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sor.size(); i++)
                  ~~^~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < b.size(); i++){
                  ~~^~~~~~~~~~
eastereggs.cpp: At global scope:
eastereggs.cpp:12:18: warning: 'cntQ' defined but not used [-Wunused-variable]
 static int N, X, cntQ;
                  ^~~~
eastereggs.cpp:12:15: warning: 'X' defined but not used [-Wunused-variable]
 static int N, X, cntQ;
               ^
eastereggs.cpp:12:12: warning: 'N' defined but not used [-Wunused-variable]
 static int N, X, cntQ;
            ^

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20