oj.uz

답안 #320432

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320432 2020-11-08T18:33:46 Z qpwoeirut Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 20 ms 740 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];
int qct;

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> qnodes;
    for (int i=0; i<N; ++i) {
        if (dist[i] <= qdist) {
            qnodes.emplace_back(i+1);
        }
    }
    assert(++qct <= 16);
    //cerr << "mid,qnodes: " << mid; for (int i=0; i<qnodes.size(); ++i) { cerr << ' ' << qnodes[i]; } cerr << endl;
    return query(qnodes);
}

vector<int> nodes, to_query;
bool check2(int start, int finish) {
    int s = nodes.size();

    nodes.insert(nodes.end(), to_query.begin() + start, to_query.begin() + finish);
    bool ret = query(nodes);
    nodes.resize(s);
    assert(++qct <= 16);
    return ret;
}

int findEgg (int n, vector<pair<int,int>> bridges) {
    N = n;
    qct = 0;
    //cerr << "N: " << N << endl;
    for (int i=0; i<N; ++i) {
        dist[i] = ct[i] = sum[i] = 0;
        adj[i].clear();
    }
    nodes.clear();
    to_query.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;
    assert(lo < to_query.size());
    return to_query[lo];
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:56: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]
   56 |     for (int i=0; i<bridges.size(); ++i) {
      |                   ~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from grader.h:1,
                 from eastereggs.cpp:2:
eastereggs.cpp:100:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     assert(lo < to_query.size());
      |            ~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 364 KB Number of queries: 7
2 Runtime error 1 ms 620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 740 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -