Submission #1106493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106493		FubuGold	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	2051 ms	411380 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const int BLOCK_SZ = 275;
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++) {
        // 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[0],make_pair(v,0)));
        }
        while (mx_dis[u].size() < BLOCK_SZ && adj_pq.size()) {
            pair<int,int> cur_mx = adj_pq.top().first,cur_id = adj_pq.top().second;
//            cout << cur_mx.first << ' ' << cur_mx.second << ' ' << cur_id.first << ' ' << cur_id.second << '\n';
            cur_mx.first++;
            if (mx_dis[u].empty() || mx_dis[u].back() != cur_mx) mx_dis[u].push_back(cur_mx);
            adj_pq.pop();
            cur_id.second++;
            if (cur_id.second >= mx_dis[cur_id.first].size()) continue;
            adj_pq.push(make_pair(mx_dis[cur_id.first][cur_id.second],cur_id));
        }
        if (mx_dis[u].size() < BLOCK_SZ) mx_dis[u].push_back(make_pair(0,u));
//        for (pair<int,int> x : st) mx_dis[u].push_back(x);
//        for (pair<int,int> x : mx_dis[u]) {
//            cout << u << ' ' << x.first << ' ' << x.second << '\n';
//        }
    }
}

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=0;i<mx_dis[id].size();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:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp:27:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |             if (cur_id.second >= mx_dis[cur_id.first].size()) continue;
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int query_big(int)':
bitaro.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j=0;j<adj[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int query(int)':
bitaro.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0;i<mx_dis[id].size();i++) {
      |                  ~^~~~~~~~~~~~~~~~~~

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