Submission #396679

#	Time	Username	Problem	Language	Result	Execution time	Memory
396679		Victor	Easter Eggs (info1cup17_eastereggs)	C++17	Compilation error	0 ms	0 KiB

eastereggs

#include <bits/stdc++.h>

#include "grader.h"

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vi graph[513], vec;
uset<int> cands, chosen;
int take;

void choose(int u, int p) {
    if (!take) return;

    if (cands.count(u)) {
        --take;
        chosen.insert(u);
    }

    trav(v, graph[u]) if (v != p) choose(v, u);
}

bool dfs(int u, int p) {
    bool ret = chosen.count(u);
    trav(v, graph[u]) if (v != p) ret |= dfs(v, u);
    if (ret) vec.pb(u);
    return ret;
}

int recurse() {
    if (!sz(cands)) return 0;

    int root = *cands.begin();
    if (sz(cands) == 1) return root;

    chosen.clear();
    take = sz(cands) >> 1;
    choose(root, root);
    vec.clear();
    dfs(root, root);

    int egg = query(vec);

    if (!egg) {
        uset<int> next;
        trav(cand, cands) if (!chosen.count(cand)) next.insert(cand);
        chosen = next;
    }

    cands = chosen;

    return recurse();
}

int findEgg(int n, vii edges) {
    cands.clear();
    fill(graph,graph+n,vi());
    trav(edge, edges) {
        int u, v;
        tie(u, v) = edge;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    rep(i, 0, n) cands.insert(i + 1);
    return recurse();
}

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;
}

int main() {
    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;
}

Compilation message (stderr)

eastereggs.cpp: In function 'int main()':
eastereggs.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
eastereggs.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
eastereggs.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |     scanf("%d", &Queries);
      |     ~~~~~^~~~~~~~~~~~~~~~
eastereggs.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%d", &X), cntQ = 0;
      |         ~~~~~^~~~~~~~~~
/tmp/ccCpOOzu.o: In function `query(std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x0): multiple definition of `query(std::vector<int, std::allocator<int> >)'
/tmp/ccq9vpoP.o:eastereggs.cpp:(.text+0x190): first defined here
/tmp/ccCpOOzu.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccq9vpoP.o:eastereggs.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status