제출 #67636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67636		ekrem	Easter Eggs (info1cup17_eastereggs)	C++11	6 / 100	18 ms	800 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, ans, u[MAXN], say[MAXN];
vi g[MAXN], sor;

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


int hazirla(int node, int par){
	say[node] = 1;
	for(int i = 0; i < g[node].size(); i++)
		if(g[node][i] != par and !u[g[node][i]])
			say[node] += hazirla(g[node][i], node);
	// cout << node << " -> " << say[node] << endl;
	return say[node];
}

void centbul(int node, int top){
	hazirla(node, node);
	int par = node, f = 1;
	while(f){
		f = 0;
		for(int i = 0; i < g[node].size(); i++)
			if(!u[g[node][i]] and g[node][i] != par and say[ g[node][i] ] > top/2){
				par = node;
				node = g[node][i];
				f = 1;
				break;
			}
	}
	ii mx = mp(-1, -1);
	for(int i = 0; i < g[node].size(); i++)
		if(!u[g[node][i]] and g[node][i] != par){
			int coc = g[node][i];
			mx = max(mx, mp(say[coc], coc));
		}
	if(mx.st == -1){
		sor.clear();
		sor.pb(node);
		if(query(sor)){
			ans = node;
			return;
		}
	}
	sor.clear();
	dfs(mx.nd, node);
	if(query(sor)){
		u[node] = 1;
		centbul(mx.nd, mx.st);
	} else{
		u[mx.nd] = 1;
		centbul(node, top - mx.st);
	}
}



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

	for(int i = 0; i < MAXN; i++){
		say[i] = u[i] = 0;
		g[i].clear();
	}

	ans = -1;
	n = N;

	for(int i = 0; i < b.size(); i++){
		g[b[i].st].pb(b[i].nd);
		g[b[i].nd].pb(b[i].st);
	}
	// hazirla(1, 1);
	centbul(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;
// }

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

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int hazirla(int, int)':
eastereggs.cpp:62: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 centbul(int, int)':
eastereggs.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[node].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
eastereggs.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < b.size(); i++){
                 ~~^~~~~~~~~~

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