Submission #897505

#	Time	Username	Problem	Language	Result	Execution time	Memory
897505		Amirreza_Fakhri	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	648 ms	404332 KiB

bitaro

// In the name of the God 
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
 
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5, sq = 500;
 
int n, m, q, dist[maxn];
bool mark[maxn];
pii dp[maxn][sq];
vector <int> adj[maxn], p[maxn];
 
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int v, u; cin >> v >> u;
        adj[--u].pb(--v);
        p[u].pb(0);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < sq; j++) dp[i][j] = mp(-1, -1);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < sq; j++) {
            int mx = -1, v = -1, googo = -1;
            for (int k = 0; k < adj[i].size(); k++) {
                if (p[i][k] < sq) {
                    if (dp[adj[i][k]][p[i][k]].F+1 > mx and dp[adj[i][k]][p[i][k]].S != -1) {
                        if (!mark[dp[adj[i][k]][p[i][k]].S]) {
                            mx = dp[adj[i][k]][p[i][k]].F+1, v = dp[adj[i][k]][p[i][k]].S;
                            googo = k;
                        }
                        else {
                            p[i][k]++;
                            k--;
                        }
                    }
                }
            }
            dp[i][j] = mp(mx, v);
            if (v != -1) mark[v] = 1;
            if (googo != -1) p[i][googo]++;
        }
        for (int j = 0; j < sq; j++) {
            if (dp[i][j].F == -1) {
                dp[i][j].F = 0, dp[i][j].S = i;
                break;
            }
            mark[dp[i][j].S] = 0;
        }
    }
    memset(mark, 0, sizeof mark);
    vector <int> ans; ans.clear();
    while (q--) {
        vector <int> vec; vec.clear();
        int v, c; cin >> v >> c; v--;
        for (int i = 0; i < c; i++) {
            int u; cin >> u; vec.pb(--u); mark[u] = 1;
        }
        if (c <= sq-5) {
            int anss = -1;
            for (int i = 0; i < sq; i++) {
                if (dp[v][i].F == -1) break;
                if (!mark[dp[v][i].S]) {
                    anss = dp[v][i].F; break;
                }
            }
            ans.pb(anss);
        }
        else {
            memset(dist, 0, sizeof dist);
            for (int i = 0; i < n; i++) {
                if (mark[i]) dist[i] = -inf;
                for (int u : adj[i]) smax(dist[i], dist[u]+1);
            }
            if (dist[v] >= 0) ans.pb(dist[v]);
            else ans.pb(-1);
        }
        for (int u : vec) mark[u] = 0;
    }
    for (int x : ans) cout << x << '\n';
    // for (int j = 0; j < 6; j++) {
    //     for (int i = 0; i < 7; i++) {
    //         cout << dp[j][i].F << ' ' << dp[j][i].S << '\n';
    //     }
    //     cout << "_______________)()(__________________\n";
    // }
    return 0;
}

/*
12 17 1
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
8 4 1 2 3 4
*/

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:38:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for (int k = 0; k < adj[i].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~

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