Submission #762158

#	Time	Username	Problem	Language	Result	Execution time	Memory
762158		myrcella	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	19 ms	464 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;

typedef long long LL;

#define F first
#define S second
#define pii pair<LL, LL>
#define pb push_back
#define debug(x) cerr << #x << "=" << x << endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a; i < (b); i++)
#define MP make_pair
#define SZ(x) (static_cast<int>(x.size()))
#define MOD 1000000007
#define ALL(x) x.begin(), x.end()
void inc(int &a, int b) {a = (a+b)%MOD;}
void dec(int &a, int b) {a = (a-b+MOD)%MOD;}
int prod(int a,int b) {return LL(a)*LL(b)%MOD;}
int lowbit(int x) {return x&(-x);}

const int maxn = 555;
vector <int> edge[maxn];
int deg[maxn];
bool mark[maxn];
bool inq[maxn];
vector <int> q, qq;
int rem;
int n;

void dfs(int u, int fa) {
  if (SZ(qq) >= rem/2) return;
  q.pb(u + 1);
  inq[u] = 1;
  if (!mark[u]) qq.pb(u);
  for (int v : edge[u]) {
	if (v == fa) continue;
	dfs(v, u);
  }
}

void solve() {
  int start;
  rep(i, 0, n) {
	if (deg[i] == 1) start = i;
	inq[i] = 0;
  }
  q.clear(), qq.clear();
  dfs(start, -1);
  int tmp = query(q);
  //for (auto it : q) debug(it);
  if (tmp == 1) {
	rep(i, 0, n) if (mark[i] == 0 and inq[i] == 0) {
	  mark[i] = 1;
	  rem--;
    }
  }
  else {
	rep(i, 0, n) if (mark[i] == 0 and inq[i] == 1) {
      mark[i] = 1;
      rem--;
    }
  }
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
	rep(i, 0, n) {
		edge[i].clear();
		mark[i] = 0;
		deg[i] = 0;
	}
	n = N;
	rep(i, 0, n-1) {
	  int u = bridges[i].F, v = bridges[i].S;
	  u--, v--;
	  edge[u].pb(v);
	  edge[v].pb(u);
	  deg[u]++;
	  deg[v]++;
	}
	rem = N;
    while (rem > 1) {
		solve();
		//debug(rem);
	}
    rep(i, 0, N) if (mark[i] == 0) return i+1;
    return -1;
}

Compilation message (stderr)

eastereggs.cpp: In function 'void solve()':
eastereggs.cpp:51:6: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   dfs(start, -1);
      |   ~~~^~~~~~~~~~~

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