Submission #521177

#	Time	Username	Problem	Language	Result	Execution time	Memory
521177		Ai7081	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	7 ms	10088 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Query{
    int town, idx;
    vector<int> busy;
    bool operator < (const Query &o) const { return town < o.town; }
};

int out[N];
set<pair<int, int>, greater<pair<int, int>>> s[N];
set<int, greater<int>> rev[N];
vector<Query> que;
bool mark[N], isbusy[N];

int dfs(int v) {
    int ret = 0;
    mark[v] = true;
    if (isbusy[v] && rev[v].empty()) return -1;
    for (auto to : rev[v]) {
        if (!mark[to]) ret = max(ret, dfs(to) + 1);
    }
    return ret;
}

int main() {
    int n, m, Q, a, b, n_busy;
    scanf(" %d %d %d", &n, &m, &Q);
    int sq = ceil(sqrt(n+.0));
    while (m--) {
        scanf(" %d %d", &a, &b);
        rev[max(a, b)].insert(min(a, b));
    }
    for (int i=1; i<=Q; i++) {
        Query in;
        in.idx = i;
        scanf(" %d %d", &in.town, &n_busy);
        while (n_busy--) {
            scanf(" %d", &a);
            in.busy.push_back(a);
        }
        que.push_back(in);
    }
    sort(que.begin(), que.end());
    int now = 1;
    for (int i=1; i<=n; i++) s[i].insert({0, i});
    fill_n(out, n+5, -1);
    for (auto q : que) {
        while (now < q.town) {
            now++;
            for (auto to : rev[now]) {
                for (auto [val, from] : s[to]) {
                    if (s[now].size() < sq) s[now].insert({val+1, from});
                    else if (val+1 > (--s[now].end())->first) {
                        s[now].erase(--s[now].end());
                        s[now].insert({val+1, from});
                    }
                }
            }
        }
        if (q.busy.size() >= sq) {
            fill_n(mark, n+5, false);
            fill_n(isbusy, n+5, false);
            for (auto it : q.busy) isbusy[it] = true;
            out[q.idx] = dfs(q.town);
            if (!out[q.idx] && isbusy[q.town]) out[q.idx] = -1;
        }
        else {
            for (auto [val, from] : s[now]) {
                auto tmp = lower_bound(q.busy.begin(), q.busy.end(), from);
                if (tmp == q.busy.end() || *tmp != from) {
                    out[q.idx] = val;
                    break;
                }
            }
        }
    }
    for (int i=1; i<=Q; i++) printf("%d\n", out[i]);

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:55:39: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int>, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |                     if (s[now].size() < sq) s[now].insert({val+1, from});
      |                         ~~~~~~~~~~~~~~^~~~
bitaro.cpp:63:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         if (q.busy.size() >= sq) {
      |             ~~~~~~~~~~~~~~^~~~~
bitaro.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf(" %d %d %d", &n, &m, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf(" %d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf(" %d %d", &in.town, &n_busy);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |             scanf(" %d", &a);
      |             ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86