oj.uz

Submission #45371

# Submission time Handle Problem Language Result Execution time Memory
45371 2018-04-13T03:40:16 Z model_code Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 24 ms 620 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = (1 << 9) + 10;

bool query(vector < int > v);

int n, all[nmax];
vector < int > g[nmax];

void dfs(int node, int dad) {
    all[++n] = node;
    for (auto &it: g[node])
        if (it != dad) dfs(it, node);
}

bool do_query(int n) {
    vector < int > res;
    for (int i = 1; i <= n; ++i)
        res.push_back(all[i]);
    return query(res);
}

void clear_(int n) {
    for (int i = 1; i <= n; ++i)
        g[i].clear();
}

int findEgg(int dim, vector < pair < int, int > > edges) {
    clear_(dim);
    for (int i = 0; i < dim - 1; ++i) {
        int x, y; tie(x, y) = edges[i];
        g[x].push_back(y); g[y].push_back(x);
    }

    n = 0; dfs(1, 0);

    int left = 1; int right = n - 1; int res = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (do_query(mid) == 1)
            res = mid, right = mid - 1;
        else left = mid + 1;
    }

    res = all[res];
    return res;
}

#ifndef EVAL
int X, Q;

int main() {
    ifstream fin("input");
    ofstream fout("output");

    int n, nr;
    vector < pair < int, int > > v;
    vector < int > Eggs;

    fin >> n >> nr; //there are nr Easter Eggs
    for (int i = 1; i <= nr; ++i) {
        int x; fin >> x; //the i-th Easter Eggs
        Eggs.push_back(x);
    }

    //the bridges
    for (int i = 1; i < n; ++i) {
        int x, y; fin >> x >> y;
        v.push_back({x, y});
    }

    for (vector < int > :: iterator it = Eggs.begin(); it != Eggs.end(); ++it) {
        Q = 0; X = *it;
        fout << findEgg(n, v) << '\n';
        fout << Q << '\n';
        fout << '\n';
    }
}

bool used[512+10], is[512+10];

void browse(int node) {
    used[node] = 1;
    for (vector < int > :: iterator it = g[node].begin(); it != g[node].end(); ++it) {
        if (used[*it]) continue;
        if (is[*it]) browse(*it);
    }
}

bool beautiful(vector < int > v) {
    int n = (int)v.size();

    memset(used, 0, sizeof(used));
    memset(is, 0, sizeof(is));

    for (int i = 0; i < n; ++i)
        is[v[i]] = 1;

    browse(v[0]);
    for (int i = 0; i < n; ++i)
        if (!used[v[i]]) return 0;
    return 1;
}

bool query(vector < int > v) {
    if (!beautiful(v)) {
        printf("The query-islands are not beautiful");
        exit(0);
    }

    bool res = 0; Q++;
    for (vector < int > :: iterator it = v.begin(); it != v.end(); ++it)
        res |= (X == *it);
    return res;
}
#endif

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Number of queries: 8
2 Correct 14 ms 584 KB Number of queries: 9
3 Correct 23 ms 584 KB Number of queries: 9
4 Correct 24 ms 584 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 584 KB Number of queries: 9
2 Correct 16 ms 584 KB Number of queries: 9
3 Correct 23 ms 584 KB Number of queries: 9
4 Correct 20 ms 620 KB Number of queries: 9