oj.uz

Submission #1002076

# Submission time Handle Problem Language Result Execution time Memory
1002076 2024-06-19T09:42:52 Z Tob Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 11 ms 504 KB 
#include <bits/stdc++.h>

#include "grader.h"

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

using namespace std;
/*
static int N, X, cntQ;
static vector < int > v[1009];

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 (auto 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 (auto 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 (auto it = h.begin (); it != h.end (); it ++)
        if (*it == X) return 1;
    return 0;
}*/

//----------------------------

const int maxn = 512;

int tim, st[maxn];
vector <int> adj[maxn];

void dfs(int x, int p = -1) {
	st[tim++] = x;
	for (int y : adj[x]) if (y != p) dfs(y, x);
}

int findEgg(int n, vector <pii> e) {
	tim = 0;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < n-1; i++) {
		adj[e[i].F-1].pb(e[i].S-1);
		adj[e[i].S-1].pb(e[i].F-1);
	}
	int lo = 0, hi = n-1;
	dfs(0);
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		vector <int> v;
		for (int i = 0; i <= mid; i++) v.pb(st[i]+1);
		if (query(v)) hi = mid;
		else lo = mid+1;
	}
	return st[lo]+1;
}

//----------------------------
/*
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "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 ({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;
}*/

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Number of queries: 8
2 Correct 6 ms 344 KB Number of queries: 9
3 Correct 11 ms 492 KB Number of queries: 9
4 Correct 11 ms 504 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Number of queries: 9
2 Correct 8 ms 344 KB Number of queries: 9
3 Correct 9 ms 484 KB Number of queries: 9
4 Correct 9 ms 344 KB Number of queries: 9