Submission #532331

#	Time	Username	Problem	Language	Result	Execution time	Memory
532331		MohamedFaresNebili	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1926 ms	415300 KiB

bitaro

#include <bits/stdc++.h>

        using namespace std;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
        using db = double;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()
        #define lb lower_bound
        #define ub upper_bound

        int n, m, q, batch = 350; vector<int> adj[100005];
        int vis[100005], vis0[100005], val[100005]; vector<ii> far[100005];
        bool cmp(int u, int v) {
            return val[u] > val[v];
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> m >> q; memset(vis, -1, sizeof vis);
            memset(vis0, -1, sizeof vis0);
            for(int l = 0; l < m; l++) {
                int u, v; cin >> u >> v;
                u--; v--; adj[v].pb(u);
            }
            for(int l = 0; l < n; l++) {
                vector<int> ve;
                for(auto u : adj[l]) {
                    for(auto v : far[u]) {
                        if(vis[v.ss] != l) {
                            vis[v.ss] = l; ve.pb(v.ss);
                            val[v.ss] = v.ff + 1;
                        }
                        else val[v.ss] = max(val[v.ss], v.ff + 1);
                    }
                    if(vis[u] != l) {
                        vis[u] = l; ve.pb(u);
                        val[u] = 1;
                    }
                }
                ve.pb(l); sort(all(ve), cmp);
                for(int i = 0; i < min((int)ve.size(), batch); i++)
                    far[l].pb({val[ve[i]], ve[i]});
            }
            while(q--) {
                int u, k; cin >> u >> k; u--;
                for(int l = 0; l < k; l++) {
                    int v; cin >> v; v--; vis0[v] = q;
                }
                if(k < batch) {
                    int res = -1;
                    for(auto v : far[u]) {
                        if(vis0[v.ss] == q) continue;
                        res = v.ff; break;
                    }
                    cout << res << "\n";
                }
                else {
                    vector<int> dp(n, -1);
                    for(int l = 0; l <= u; l++) {
                        if(vis0[l] != q) dp[l] = max(dp[l], 0);
                        for(auto v : adj[l]) {
                            if(dp[v] != -1) dp[l] = max(dp[l], dp[v] + 1);
                        }
                    }
                    cout << dp[u] << "\n";
                }
            }
        }

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