Submission #1106485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106485		FubuGold	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2104 ms	275312 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const int BLOCK_SZ = 350;
int n,m,q;
vector<int> adj[MAXN+1]; // rev_adj
vector<pair<int,int>> mx_dis[MAXN+1];

void precomp() {
    for (int u=1;u<=n;u++) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        // pls dont do this
        priority_queue<pair<pair<int,int>,pair<int,int>>> adj_pq;
        for (int i=0;i<adj[u].size();i++) {
            int v = adj[u][i];
            vector<pair<int,int>> &vec = mx_dis[v];
            adj_pq.push(make_pair(vec.back(),make_pair(v,vec.size()-1)));
        }
        while (pq.size() < BLOCK_SZ && adj_pq.size()) {
            pair<int,int> cur_mx = adj_pq.top().first,cur_id = adj_pq.top().second;
            cur_mx.first++;
            pq.push(cur_mx);
            adj_pq.pop();
            cur_id.second--;
            if (cur_id.second < 0) continue;
            adj_pq.push(make_pair(mx_dis[cur_id.first][cur_id.second],cur_id));
        }
        if (pq.size() < BLOCK_SZ) pq.push(make_pair(0,u));
        while (pq.size()) {
//            cerr << u << ' ' << pq.top().first << ' ' << pq.top().second << '\n';
            mx_dis[u].push_back(pq.top());
            pq.pop();
        }
    }
}

int dp[MAXN+1];
bool no_no[MAXN+1];

int query_big(int id) {
    memset(dp,-1,sizeof(dp));
    for (int i=1;i<=id;i++) {
        if (!no_no[i]) dp[i] = 0;
        for (int j=0;j<adj[i].size();j++) {
            int v = adj[i][j];
            if (dp[v] == -1) continue;
            dp[i] = max(dp[i],dp[v] + 1);
        }
    }
    return dp[id];
}

int query(int id) {
    for (int i=mx_dis[id].size()-1;i>=0;i--) {
        if (!no_no[mx_dis[id][i].second]) return mx_dis[id][i].first;
    }
    if (mx_dis[id].size() < BLOCK_SZ) return -1;
    return query_big(id);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        int x,y; cin >> x >> y;
        adj[y].push_back(x);
    }
    precomp();
    while (q--) {
        int t,y;
        vector<int> c;
        cin >> t >> y;
        for (int i=0;i<y;i++) {
            int x; cin >> x;
            c.push_back(x);
            no_no[x] = 1;
        }
        cout << query(t) << '\n';
        for (int i=0;i<y;i++) no_no[c[i]] = 0;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void precomp()':
bitaro.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int query_big(int)':
bitaro.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j=0;j<adj[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~

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