Submission #521219

#	Time	Username	Problem	Language	Result	Execution time	Memory
521219		Ai7081	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2011 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];
vector<int> adj[N], rev[N];
vector<Query> que;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m, Q, a, b, n_busy;
    //scanf(" %d %d %d", &n, &m, &Q);
    cin >> n >> m >> Q;
    int sq = ceil(sqrt(n+.0));
    while (m--) {
        //scanf(" %d %d", &a, &b);
        cin >> a >> b;
        rev[max(a, b)].push_back(min(a, b));
        adj[min(a, b)].push_back(max(a, b));
    }
    for (int i=1; i<=n; i++) sort(rev[i].begin(), rev[i].end(), greater<int>());
    for (int i=1; i<=Q; i++) {
        Query in;
        in.idx = i;
        //scanf(" %d %d", &in.town, &n_busy);
        cin >> in.town >> n_busy;
        while (n_busy--) {
            //scanf(" %d", &a);
            cin >> 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, Q+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});
                    }
                    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:51: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]
   51 |                     if (s[now].size() < sq) s[now].insert({val+1, from});
      |                         ~~~~~~~~~~~~~~^~~~
bitaro.cpp:60:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if (q.busy.size() >= sq) {
      |             ~~~~~~~~~~~~~~^~~~~

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