oj.uz

Submission #762158

# Submission time Handle Problem Language Result Execution time Memory
762158 2023-06-21T02:24:02 Z myrcella Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 19 ms 464 KB 
#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

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.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 464 KB Number of queries: 8
2 Correct 9 ms 336 KB Number of queries: 9
3 Correct 13 ms 352 KB Number of queries: 9
4 Correct 13 ms 336 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 380 KB Number of queries: 9
2 Correct 17 ms 336 KB Number of queries: 9
3 Correct 19 ms 348 KB Number of queries: 9
4 Correct 18 ms 364 KB Number of queries: 9