Submission #918398

#	Time	Username	Problem	Language	Result	Execution time	Memory
918398		ShaShi	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1542 ms	464696 KiB

bitaro

#include <bits/stdc++.h>
// #define int long long 
#define F first
#define S second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pb push_back
#define endl "\n"
 
 
using namespace std;
typedef long long ll;
 
const int MAXN = (int)1e6 + 7;
const int MOD = 999999893;
const int INF = (int)1e9 + 7;
const int SQ = 350;
 
 
int n, m, t, flag, u, v, w, k, tmp, tmp2, tmp3, tmp4, tmp5, tmp6, ans, q, ans2;
int arr[MAXN], cnt2[MAXN], love[MAXN];
bool hate[MAXN], op[MAXN];
vector<pii> vec[MAXN]; vector<int> adj[MAXN]; vector<int> tvec;



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++) {
        cin >> u >> v;

        adj[v].pb(u);
    }

    
    fill(arr, arr+n+7, -1);

    for (int i=1; i<=n; i++) {
        vec[i].pb(mp(0, i)); tvec.clear();

        for (int u:adj[i]) {
            for (auto cur:vec[u]) {
                if (arr[cur.S] == -1) {
                    arr[cur.S] = cur.F;
                    tvec.pb(cur.S);
                } else if (cur.F > arr[cur.S]) {
                    arr[cur.S] = cur.F;
                }
            }
        }

        for (int u:tvec) vec[i].pb(mp(arr[u]+1, u)), arr[u] = -1;
        sort(all(vec[i]), greater<pii>());
        while (vec[i].size() > SQ) vec[i].pop_back();

        // cout << "#" << i << endl;
        // for (auto cur:vec[i]) cout << "@" << cur.F << " " << cur.S << endl;
    }


    while (q--) {
        cin >> v >> w; 
        tvec.clear();

        for (int i=0; i<w; i++) {
            cin >> u; 
            tvec.pb(u); op[u] = 1;
        }

        // cout << "!";

        if (w < SQ) {
            ans = -1;

            for (auto cur:vec[v]) {
                if (!op[cur.S]) {
                    ans = cur.F;
                    break;
                }
            }

            cout << ans << endl;
        } else {
            for (int i=1; i<=v; i++) {
                love[i] = (op[i]? -1 : 0);
                for (int u:adj[i]) if (love[u] != -1 && love[u]+1 > love[i]) love[i] = love[u]+1;
            }

            cout << love[v] << endl;
        }

        for (int i=0; i<w; i++) op[tvec[i]] = 0;
    }


    return 0;
}

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