Submission #1326530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326530		johnadil	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	782 ms	257568 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 seen[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]);
        }
        if (d[i] == -1) continue;
        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);
    }
    
    int timer = 0;
    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]) {
            ++timer;
            tmp.clear();
            int ptr1 = 0, ptr2 = 0;
            for (;ptr1 < paths[i].size() && ptr2 < paths[to].size() && tmp.size() <= B;) {
                if (seen[paths[i][ptr1].second] == timer) {
                    ++ptr1;
                    continue;
                }
                if (seen[paths[to][ptr2].second] == timer) {
                    ++ptr2;
                    continue;
                }
                if (paths[i][ptr1].first > paths[to][ptr2].first + 1) {
                    seen[paths[i][ptr1].second] = timer;
                    tmp.push_back(paths[i][ptr1++]);
                } else {
                    seen[paths[to][ptr2].second] = timer;
                    tmp.push_back(make_pair(paths[to][ptr2].first + 1, paths[to][ptr2].second));
                    ++ptr2;
                }
            }
            while (ptr1 < paths[i].size() && tmp.size() <= B) {
                if (seen[paths[i][ptr1].second] != timer) {
                    seen[paths[i][ptr1].second] = timer;
                    tmp.push_back(paths[i][ptr1]);
                }
                ++ptr1;
            }
            while (ptr2 < paths[to].size() && tmp.size() <= B) {
                if (seen[paths[to][ptr2].second] != timer) {
                    seen[paths[to][ptr2].second] = timer;
                    tmp.push_back(make_pair(paths[to][ptr2].first + 1, paths[to][ptr2].second));
                }
                ++ptr2;
            }
            
            paths[i] = tmp;
        }
    }
    
    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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86