제출 #1290520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290520		AutomatiC__	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1135 ms	411388 KiB

bitaro

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <deque>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 100005;
vector<int> g[maxn];
vector<pair<int, int> > path[maxn];
int n, m, q;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[y].push_back(x);
    }
    int B = min((int)sqrt(n + 1), 300);
    vector<int> dis(n + 1, 0);
    for (int u = 1; u <= n; u++) {
        path[u].push_back(make_pair(0, u));
        vector<int> port;
        for (int v : g[u]) {
            for (auto [w, k] : path[v]) {
                if (!dis[k]) {
                    dis[k] = -w + 1;
                    port.push_back(k);
                } else {
                    dis[k] = max(-w + 1, dis[k]);
                }
            }
        }
        for (int v : port) {
            path[u].push_back(make_pair(-dis[v], v));
            dis[v] = 0;
        }
        sort(path[u].begin(), path[u].end());
        while (path[u].size() > B) path[u].pop_back();
        // cout << path[u].size() << endl;
    }
    vector<int> cut(n + 1, 0);
    while (q--) {
        int x, y;
        cin >> x >> y;
        vector<int> c(y + 1, 0);
        for (int i = 1; i <= y; i++) {
            cin >> c[i];
            cut[c[i]] = 1;
        }
        if (y >= B) {
            int ans = -1;
            vector<int> f(n + 1, 0);
            for (int u = x; u; u--) {
                if (u != x && !f[u]) continue;
                if (!cut[u]) ans = max(ans, f[u]);
                for (int v : g[u]) f[v] = max(f[v], f[u] + 1);
            }
            cout << ans << "\n";
            // cout << "!1\n";
        } else {
            int ans = -1;
            for (auto [w, v] : path[x]) {
                // cout << x << " " << v << " " << -w << endl;
                if (!cut[v]) {
                    ans = -w;
                    break;
                }
            }
            cout << ans << "\n";
            // cout << "!2\n";
        }
        for (int i = 1; i <= y; i++) cut[c[i]] = 0;
    }
    return 0;
}

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