oj.uz

Submission #320441

# Submission time Handle Problem Language Result Execution time Memory
320441 2020-11-08T18:58:19 Z qpwoeirut Easter Eggs (info1cup17_eastereggs) C++17
66 / 100
 44 ms 1644 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int MN = 515;

int NN;
int dist[MN], ct[MN], sum[MN];
set<int> adj[MN];
int mem[MN], mem2[MN][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) {
    if (mem[mid] != -1) return mem[mid];
    int qdist = lower_bound(sum, sum+NN, mid) - sum;
    vector<int> qnodes;
    for (int i=0; i<NN; ++i) {
        if (dist[i] <= qdist) {
            qnodes.emplace_back(i+1);
        }
    }
    //cerr << "mid,qnodes: " << mid; for (int i=0; i<qnodes.size(); ++i) { cerr << ' ' << qnodes[i]; } cerr << endl;
    mem[mid] = query(qnodes);
    return mem[mid];
}

vector<int> nodes, to_query;
bool check2(int start, int finish) {
    if (mem2[start][finish] != -1) return mem2[start][finish];
    int s = nodes.size();

    assert(finish <= to_query.size());
    nodes.insert(nodes.end(), to_query.begin() + start, to_query.begin() + finish);
    mem2[start][finish] = query(nodes);
    nodes.resize(s);
    return mem2[start][finish];
}

int findEgg (int n, vector<pair<int,int>> bridges) {
    NN = n;
    //cerr << "NN: " << N << endl;
    for (int i=0; i<MN; ++i) {
        dist[i] = ct[i] = sum[i] = 0;
        adj[i].clear();
        mem[i] = -1;
        for (int j=0; j<MN; ++j) {
            mem2[i][j] = -1;
        }
    }
    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<NN; ++i) {
        sum[i] = sum[i-1] + ct[i];
    }

    int lo = 1, hi = NN+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+NN, lo) - sum;
    //cerr << "depth: " << egg_depth << endl;

    for (int i=0; i<NN; ++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];
}
/*
16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

16
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11 
11 12 
12 13
13 14
14 15
15 16
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

16
1 2
2 3
3 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11 
4 12 
4 13
13 14
14 15
15 16
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
*/

Compilation message

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: In function 'bool check2(int, int)':
eastereggs.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     assert(finish <= to_query.size());
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:61: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]
   61 |     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:104:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     assert(lo < to_query.size());
      |            ~~~^~~~~~~~~~~~~~~~~

Subtask #1
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 1388 KB Number of queries: 7
2 Partially correct 5 ms 1388 KB Number of queries: 7
3 Partially correct 7 ms 1516 KB Number of queries: 8
4 Partially correct 5 ms 1388 KB Number of queries: 8

Subtask #2
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 1644 KB Number of queries: 10
2 Partially correct 33 ms 1388 KB Number of queries: 16
3 Partially correct 41 ms 1508 KB Number of queries: 14
4 Partially correct 44 ms 1516 KB Number of queries: 18

Subtask #3
13.2 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 37 ms 1516 KB Number of queries: 12
2 Partially correct 39 ms 1516 KB Number of queries: 16
3 Partially correct 41 ms 1516 KB Number of queries: 14
4 Partially correct 44 ms 1524 KB Number of queries: 17