Submission #1326524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326524		johnadil	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	2 ms	1336 KiB

bitaro

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>

using namespace std;

const int MAX_N = 100500;
const int B = 316;

int n, m, q;
vector<int> adj[MAX_N];
vector<pair<int, int>> paths[MAX_N];
bool is_allowed[MAX_N];
bool used[MAX_N];
int d[MAX_N];

int heavy_ans(int t) {
    int ans = -1;
    memset(d, -1, sizeof d);
    d[t] = 0;
    for (int i = t;i >= 0;--i) {
        if (is_allowed[i]) {
            ans = max(ans, d[i]);
        }
        for (auto to: adj[i]) {
            d[to] = max(d[to], d[i] + 1);
        }
    }
    return ans;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    cin >> n >> m >> q;
    for (int i = 0;i < m;++i) {
        int f, t;
        cin >> f >> t;
        --f; --t;
        adj[t].push_back(f);
    }
    
    vector<pair<int, int>> tmp;
    for (int i = 0;i < n;++i) {
        paths[i].push_back(make_pair(0, i));
        for (auto to: adj[i]) {
            tmp.clear();
            int ptr1 = 0, ptr2 = 0;
            for (;ptr1 < paths[i].size() && ptr2 < paths[to].size() && tmp.size() <= B;) {
                if (used[paths[i][ptr1].second]) {
                    ++ptr1;
                    continue;
                }
                if (used[paths[to][ptr2].second]) {
                    ++ptr2;
                    continue;
                }
                if (paths[i][ptr1].first > paths[to][ptr2].first + 1) {
                    used[paths[i][ptr1].second] = true;
                    tmp.push_back(paths[i][ptr1++]);
                } else {
                    used[paths[to][ptr2].second] = true;
                    tmp.push_back(make_pair(paths[to][ptr2].first + 1, paths[to][ptr2].second));
                    ++ptr2;
                }
            }
            while (ptr1 < paths[i].size() && tmp.size() <= B) {
                if (!used[paths[i][ptr1].second]) {
                    used[paths[i][ptr1].second] = true;
                    tmp.push_back(paths[i][ptr1]);
                }
                ++ptr1;
            }
            while (ptr2 < paths[to].size() && tmp.size() <= B) {
                if (!used[paths[to][ptr2].second]) {
                    used[paths[to][ptr2].second] = true;
                    tmp.push_back(make_pair(paths[to][ptr2].first + 1, paths[to][ptr2].second));
                }
                ++ptr2;
            }
            
            paths[i] = tmp;
            for (auto [length, id]: paths[i]) {
                used[id] = false;
            }
        }
        // cout << i << ": ";
        // for (auto [length, id]: paths[i]) {
        //     cout << "[" << length << ":" << id << "] ";
        // }
        // cout << endl;
    }
    
    int t, y;
    vector<int> c;
    memset(is_allowed, 1, sizeof is_allowed);
    for (int i = 0;i < q;++i) {
        cin >> t >> y;
        --t;
        c.resize(y);
        for (int i = 0;i < y;++i) {
            cin >> c[i];
            --c[i];
            is_allowed[c[i]] = false;
        }
        if (y <= B) {
            int ans = -1;
            for (auto [length, id]: paths[t]) {
                if (is_allowed[id]) {
                    ans = length;
                    break;
                }
            }
            cout << ans << endl;
        } else {
            cout << heavy_ans(t) << endl;
        }
        for (int i = 0;i < y;++i) {
            is_allowed[c[i]] = true;
        }
    }
}

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