Submission #233429

#	Time	Username	Problem	Language	Result	Execution time	Memory
233429		DS007	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2072 ms	209448 KiB

bitaro

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

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

void pre() {
    for (int i = 0; i < n; i++) {
        priority_queue<pair<int, int>> pq;
        for (int j : adj[i]) {
            for (auto k : far[j])
                pq.push(k);
        }

        unordered_set<int> s;
        for (int j = 0; j <= ceil(sqrt(n)) && !pq.empty();) {
            auto temp = pq.top();
            pq.pop();

            if (!s.count(temp.second)) {
                far[i].emplace_back(temp.first + 1, temp.second);
                s.insert(temp.second);
                j++;
            }
        }

        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, -1e18);
    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)))
            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 'long long int solveTestCase(long long int)':
bitaro.cpp:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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