Submission #1106474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106474		FubuGold	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2084 ms	282256 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;
        pq.push(make_pair(0,u));
        for (int i=0;i<adj[u].size();i++) {
            int v = adj[u][i];
            vector<pair<int,int>> &vec = mx_dis[v];
            for (int j=0;j<vec.size();j++) {
                pair<int,int> cur = vec[j];
                cur.first++;
                if (pq.size() < BLOCK_SZ || cur.first > pq.top().first) {
                    if (pq.size() == BLOCK_SZ) pq.pop();
                    pq.push(cur);
                }
            }
        }
        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: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:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |             for (int j=0;j<vec.size();j++) {
      |                          ~^~~~~~~~~~~
bitaro.cpp: In function 'int query_big(int)':
bitaro.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j=0;j<adj[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~

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