Submission #476726

#	Time	Username	Problem	Language	Result	Execution time	Memory
476726		dooompy	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2087 ms	410760 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> invalid(n + 5, 0);
    for (int i = 1; i <= q; i++) {
        int x, y; cin >> x >> y;
        for (int j = 0; j < y; j++) {
            int cur; cin >> cur;
            invalid[cur] = i;
        }

        if(x < SQRT) {
            bool found = false;
            for (auto a : root[x]) {
                if (invalid[a.first] == i) continue;
                found = true;
                cout << a.second << "\n";
                    break;
            }
            if (!found) {
                cout << -1 << "\n";
            }
        } else {
            for (int j = 1; j <= n; j++) {
                if (invalid[j] == i) dp[j] = -1;
                else dp[j] = 0;
                for (auto a : adj[j]) {
                    if (dp[a] >= 0) dp[j] = max(dp[j], dp[a] + 1);
                }
            }
            cout << dp[x] << "\n";
        }
    }
}

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