Submission #521195

#	Time	Username	Problem	Language	Result	Execution time	Memory
521195		Ai7081	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	1880 ms	524292 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 dp[N], out[N];
set<pair<int, int>, greater<pair<int, int>>> s[N];
set<int, greater<int>> rev[N];
vector<int> adj[N];
vector<Query> que;

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));
        adj[min(a, b)].push_back(max(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]) {
                    auto tmp = s[now].end();
                    tmp--;
                    if (s[now].size() < sq) s[now].insert({val+1, from});
                    else if (val+1 > tmp->first) {
                        s[now].erase(tmp);
                        s[now].insert({val+1, from});
                    }
                    else break;
                }
            }
        }
        if (q.busy.size() >= sq) {
            fill_n(dp, q.town+5, 0);
            for (auto it : q.busy) dp[it] = -1;
            for (int i=1; i<=q.town; i++) {
                if (dp[i] == -1) continue;
                for (auto to : adj[i]) dp[to] = max(dp[to], dp[i] + 1);
            }
            out[q.idx] = dp[q.town];
        }
        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<=n; i++) {
        printf("set %d : ", i);
        for (auto it : s[i]) printf("(%d %d) ", it.first, it.second);
        printf("\n");
    }
    */
    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:48: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]
   48 |                     if (s[now].size() < sq) s[now].insert({val+1, from});
      |                         ~~~~~~~~~~~~~~^~~~
bitaro.cpp:57:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         if (q.busy.size() >= sq) {
      |             ~~~~~~~~~~~~~~^~~~~
bitaro.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf(" %d %d %d", &n, &m, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf(" %d %d", &in.town, &n_busy);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             scanf(" %d", &a);
      |             ~~~~~^~~~~~~~~~~

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