Submission #468789

#	Time	Username	Problem	Language	Result	Execution time	Memory
468789		duyanh1704	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1852 ms	414544 KiB

bitaro

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int maxN = 1e5;
const int blockSize = 350;
typedef pair<int, int> ii;
int n, m, q;
int dp[maxN + 5];
vector<int> pre[maxN + 5];
vector<ii> root[maxN + 5];

bool maximize(int &x, int y){
    return (y > x ? x = y, 1 : 0);
}

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 : pre[i]){
            for (auto e : root[j]){
                int k = e.x, c = e.y;
                if (visited[k] == i)
                    maximize(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()), blockSize);
        for (int j = 0; j < sz; ++j){
            int p = r[j];
            root[i].push_back({p, cost[p]});
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        pre[v].push_back(u);
    }
    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 < blockSize){
            bool f = 0;
            for (auto e : root[t]){
                if (queries[e.x] == i) continue;
                cout << e.y << '\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 : pre[j])
                    if (dp[k] >= 0) maximize(dp[j], dp[k] + 1);
            }
            cout << dp[t] << '\n';
        }
    }
    return 0;
}

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