Submission #1106506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106506		FubuGold	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1907 ms	211504 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100000;
const int BLOCK_SZ = 250;
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)));
        }
        vector<pair<int,int>> &cur_vec = mx_dis[u];
        while (cur_vec.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 (cur_vec.empty() || cur_vec.back() != cur_mx) cur_vec.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 (cur_vec.size() < BLOCK_SZ) cur_vec.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];
int timeVst = 0;
int 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] != timeVst) 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) {
    vector<pair<int,int>> &cur_vec = mx_dis[id];
    for (int i=0;i<cur_vec.size();i++) {
        if (no_no[cur_vec[i].second] != timeVst) return cur_vec[i].first;
    }
    if (cur_vec.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--) {
        timeVst++;
        int t,y;
        cin >> t >> y;
        for (int i=0;i<y;i++) {
            int x; cin >> x;
            no_no[x] = timeVst;
        }
        cout << query(t) << '\n';
    }
    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:28: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]
   28 |             if (cur_id.second >= mx_dis[cur_id.first].size()) continue;
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int query_big(int)':
bitaro.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int j=0;j<adj[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp: In function 'int query(int)':
bitaro.cpp:58: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]
   58 |     for (int i=0;i<cur_vec.size();i++) {
      |                  ~^~~~~~~~~~~~~~~

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