Submission #233431

#	Time	Username	Problem	Language	Result	Execution time	Memory
233431		DS007	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2115 ms	465804 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++) {
        int p[adj[i].size()] = {};
        unordered_set<int> s;

        while (s.size() <= ceil(sqrt(n))) {
            pair<pair<int, int>, int> ans = {{-1, -1}, - 1};
            for (int j = 0; j < adj[i].size(); j++) {
                if (p[j] < far[adj[i][j]].size() && ans.first < far[adj[i][j]][p[j]] && !s.count(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]++;
                s.insert(ans.first.second);
            } else break;
        }

        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 'void pre()':
bitaro.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[i].size(); j++) {
                             ~~^~~~~~~~~~~~~~~
bitaro.cpp:18: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]] && !s.count(far[adj[i][j]][p[j]].second))
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'long long int solveTestCase(long long int)':
bitaro.cpp:88:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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