Submission #233441

#	Time	Username	Problem	Language	Result	Execution time	Memory
233441		DS007	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1924 ms	414328 KiB

bitaro

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

const int N = 1e5;
int n, m, q;
vector<int> adj[N];
vector<pair<int, int>> far[N];

void pre() {
    bool allowed[n];
    fill(allowed, allowed + n, true);

    for (int i = 0; i < n; i++) {
        int p[adj[i].size()] = {};
        int count = 0;
        vector<int> used;

        while (count <= ceil(sqrt(n)) + 1) {
            pair<pair<int, int>, int> ans = {{-1, -1}, - 1};
            for (int j = 0; j < adj[i].size(); j++) {
                while (p[j] < far[adj[i][j]].size() && !allowed[far[adj[i][j]][p[j]].second])
                    p[j]++;
                if (p[j] < far[adj[i][j]].size() && ans.first < far[adj[i][j]][p[j]] && allowed[far[adj[i][j]][p[j]].second])
                    ans = {far[adj[i][j]][p[j]], j};
            }

            if (ans.first.first != -1) {
                far[i].emplace_back(ans.first.first + 1, ans.first.second);
                p[ans.second]++;
                allowed[ans.first.second] = false;
                used.push_back(ans.first.second);
                count++;
            } else break;
        }

        for (int j : used)
            allowed[j] = true;

        if (far[i].size() <= ceil(sqrt(n)))
            far[i].emplace_back(0, i);
    }
}

int calc(int t, const set<int>& c) {
    int dp[n] = {};
    fill(dp, dp + n, -1e9);
    dp[t] = 0;

    for (int i = t; i >= 0; i--) {
        for (int j : adj[i])
            dp[j] = max(dp[j], dp[i] + 1);
    }

    int ans = -1;
    for (int i = t; i >= 0; i--) {
        if (!c.count(i))
            ans = max(ans, dp[i]);
    }

    return ans;
}

int find(int t, const set<int>& c) {
    for (auto i : far[t]) {
        if (!c.count(i.second))
            return i.first;
    }
    return -1;
}

int solveTestCase(int test) {
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int s = 0, e = 0;
        cin >> s >> e;
        s--, e--;
        adj[e].push_back(s);
    }

    pre();

    for (int i = 0; i < q; i++) {
        int t = 0, y = 0;
        cin >> t >> y;

        set<int> c;
        for (int j = 0; j < y; j++) {
            int temp = 0;
            cin >> temp;
            c.insert(temp - 1);
        }

        if (y >= floor(sqrt(n)) - 1)
            cout << calc(t - 1, c) << "\n";
        else
            cout << find(t - 1, c) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message (stderr)

bitaro.cpp: In function 'void pre()':
bitaro.cpp:20:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[i].size(); j++) {
                             ~~^~~~~~~~~~~~~~~
bitaro.cpp:21:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while (p[j] < far[adj[i][j]].size() && !allowed[far[adj[i][j]][p[j]].second])
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:23:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (p[j] < far[adj[i][j]].size() && ans.first < far[adj[i][j]][p[j]] && allowed[far[adj[i][j]][p[j]].second])
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int solveTestCase(int)':
bitaro.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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