oj.uz

Submission #320428

# Submission time Handle Problem Language Result Execution time Memory
320428 2020-11-08T18:18:25 Z qpwoeirut Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 3 ms 1004 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int MN = 515;

int N;
int dist[MN], ct[MN], sum[MN];
set<int> adj[MN];

void dfs(int node, int par) {
    for (auto it=adj[node].begin(); it!=adj[node].end(); ++it) {
        if (*it == par) continue;
        dist[*it] = dist[node] + 1;
        dfs(*it, node);
    }
    ++ct[dist[node]];
}

bool check(int mid) {
    int qdist = lower_bound(sum, sum+N, mid) - sum;
    vector<int> nodes;
    for (int i=0; i<N; ++i) {
        if (dist[i] <= qdist) nodes.emplace_back(i+1);
    }
    //cerr << "mid,nodes: " << mid; for (int i=0; i<nodes.size(); ++i) { cerr << ' ' << nodes[i]; } cerr << endl;
    return query(nodes);
}

vector<int> nodes, to_query;
bool check2(int start, int finish) {
    vector<int> cpy(nodes.begin(), nodes.end());
    cpy.insert(cpy.end(), to_query.begin() + start, to_query.begin() + finish);

    return query(cpy);
}

int findEgg (int n, vector<pair<int,int>> bridges) {
    N = n;
    //cerr << "N: " << N << endl;
    for (int i=0; i<N; ++i) {
        dist[i] = ct[i] = sum[i] = 0;
        adj[i].clear();
    }
    for (int i=0; i<bridges.size(); ++i) {
        int u = bridges[i].first, v = bridges[i].second;
        --u; --v;
        adj[u].emplace(v);
        adj[v].emplace(u);
    }

    dist[0] = 0;
    dfs(0, -1);
    sum[0] = ct[0];
    for (int i=1; i<N; ++i) {
        if (ct[i] == 0) break;
        sum[i] = sum[i-1] + ct[i];
    }

    int lo = 1, hi = N+1; 
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (!check(mid)) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    int egg_depth = lower_bound(sum, sum+N, lo) - sum;
    //cerr << "depth: " << egg_depth << endl;

    for (int i=0; i<N; ++i) {
        //cerr << "i: " << i << endl;
        if (dist[i] < egg_depth) nodes.emplace_back(i+1);
        if (dist[i] == egg_depth) to_query.emplace_back(i+1);
    }

    lo = 0, hi = to_query.size();
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        //cerr << "mid: " << mid << endl;
        if (!check2(lo, mid+1)) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    //cerr << "lo: " << lo << endl;
    return to_query[lo];
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0; i<bridges.size(); ++i) {
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1004 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -