Submission #674377

#	Time	Username	Problem	Language	Result	Execution time	Memory
674377		Kahou	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	932 ms	256988 KiB

bitaro

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 1e9 + 50;
const int N = 1e5 + 50, SQ = 315;
int n, m, q, pd[N];
bool vis[N];
pii dp[N][SQ], tmp[SQ];
vector<int> adj[N];

void push(int u, int v) {
        int p1 = 0, p2 = 0, pt = 0;
        while (pt < SQ && p1 < SQ && p2 < SQ) {
                if (dp[v][p1].F > dp[u][p2].F) {
                        if (dp[v][p1].F < 0 || !vis[dp[v][p1].S]) tmp[pt++] = dp[v][p1], vis[dp[v][p1].S] = 1;
                        p1++;
                }
                else {
                        if (dp[u][p2].F < 0 || !vis[dp[u][p2].S]) tmp[pt] = dp[u][p2], tmp[pt].F++, pt++, vis[dp[u][p2].S] = 1;
                        p2++;
                }
        }
        while (pt < SQ && p1 < SQ) {
                if (dp[v][p1].F < 0 || !vis[dp[v][p1].S]) tmp[pt++] = dp[v][p1], vis[dp[v][p1].S] = 1;
                p1++;
        }
        while (pt < SQ && p2 < SQ) {
                if (dp[u][p2].F < 0 || !vis[dp[u][p2].S]) tmp[pt] = dp[u][p2], tmp[pt].F++, pt++, vis[dp[u][p2].S] = 1;
                p2++;
        }
        for (int i = 0; i < SQ; i++) {
                dp[v][i] = tmp[i];
                vis[tmp[i].S] = 0;
        }
}
void solve() {
        cin >> n >> m >> q;
        for (int i = 1; i <= m; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
        }
        for (int u = 1; u <= n; u++) {
                sort(adj[u].begin(), adj[u].end());
                adj[u].resize(unique(adj[u].begin(), adj[u].end())-adj[u].begin());
                dp[u][0] = {0, u};
                for (int i = 1; i < SQ; i++) {
                        dp[u][i] = {-inf, 0};
                }
        }
        for (int u = 1; u <= n; u++) {
                for (int v:adj[u]) {
                        push(u, v);
                }
        }
        vector<int> vc;
        while (q--) {
                int x, s;
                cin >> x >> s;
                vc.clear();
                int ans = 0;
                for (int i = 1; i <= s; i++) {
                        int v;
                        cin >> v;
                        vc.push_back(v);
                }
                if (s < SQ) {
                        for (int u:vc) vis[u] = 1;
                        for (int i = 0; i < SQ; i++) {
                                if (vis[dp[x][i].S]) continue;
                                ans = dp[x][i].F;
                                break;
                        }
                        for (int u:vc) vis[u] = 0;
                }
                else {
                        for (int u = 1; u <= n; u++) pd[u] = 0;
                        for (int u:vc) pd[u] = -inf;
                        for (int u = 1; u <= n; u++) {
                                for (int v:adj[u]) {
                                        pd[v] = max(pd[v], pd[u]+1);
                                }
                        }
                        ans = pd[x];
                }
                cout << (ans < 0? -1 : ans) << endl;
        }
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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