Submission #476727

#	Time	Username	Problem	Language	Result	Execution time	Memory
476727		dooompy	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1849 ms	414432 KiB

bitaro

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int SQRT = 350;
const int maxN = 1e5;

int dp[maxN + 5];
vector<int> adj[maxN + 5];
vector<pair<int, int>> root[maxN + 5];

int n, m, q;

void build(){
    vector<int> cost(n + 5, 0);
    vector<int> visited(n + 5, -1);

    for (int i = 1; i <= n; ++i){
        vector<int> r;
        for (int j : adj[i]){
            for (auto e : root[j]){
                int k = e.first, c = e.second;
                if (visited[k] == i)
                    cost[k]= max(cost[k], c + 1);
                else{
                    r.push_back(k);
                    cost[k] = c + 1;
                    visited[k] = i;
                }
            }
            if (visited[j] != i){
                r.push_back(j);
                cost[j] = 1;
                visited[j] = i;
            }
        }
        r.push_back(i);

        sort(r.begin(), r.end(), [&](int a, int b){
            return (cost[a] > cost[b]);
        });
        int sz = min(int(r.size()), SQRT);
        for (int j = 0; j < sz; ++j){
            int p = r[j];
            root[i].push_back({p, cost[p]});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[b].push_back(a);
    }

//    vector<int> dist(n + 5, 0);
//    vector<int> seen(n + 5, -1);
//    for (int i = 1; i <= n; i++) {
//        vector<int> temp;
//        for (auto a : adj[i]) {
//            for (auto b : root[a]) {
//                int k = b.second, c = b.first;
//                if (seen[k] != i) {
//                    seen[k] = i;
//                    dist[k] = c + 1;
//                    temp.push_back(k);
//                } else {
//                    dist[k] = max(dist[k], c + 1);
//                }
//            }
//            if (seen[a] != i) {
//                temp.push_back(a);
//                dist[a] = 1;
//                seen[a] = i;
//            }
//        }
//
//        temp.push_back(i);
//
//        sort(temp.begin(), temp.end(), [&](int a, int b) {
//            return dist[a] > dist[b];
//        });
//
//        int sz = min(SQRT, (int) temp.size());
//        for (int j = 0; j < sz; j++) {
//            root[i].push_back({dist[temp[j]], temp[j]});
//        }
//    }

    build();

    vector<int> queries(n + 5, 0);

    for (int i = 1; i <= q; ++i){
        int t; cin >> t;
        int sz; cin >> sz;
        for (int j = 1; j <= sz; ++j){
            int x; cin >> x;
            queries[x] = i;
        }

        if (sz < SQRT){
            bool f = 0;
            for (auto e : root[t]){
                if (queries[e.first] == i) continue;
                cout << e.second << '\n';
                f = 1;
                break;
            }
            if (!f) cout << -1 << '\n';
        }
        else{
            for (int j = 1; j <= n; ++j){
                if (queries[j] != i) dp[j] = 0;
                else dp[j] = -1;
                for (int k : adj[j])
                    if (dp[k] >= 0) dp[j] = max(dp[j], dp[k] + 1);
            }
            cout << dp[t] << '\n';
        }
    }
    return 0;
}

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