Submission #863870

#	Time	Username	Problem	Language	Result	Execution time	Memory
863870		biximo	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	813 ms	93012 KiB

bitaro

#include <bits/stdc++.h>
#define N 100005
#define BL 100
using namespace std;
typedef pair<int, int> pi;
int n, m, q;
vector<int> paths[N], NOT;
vector<pi> dp[N];
bool added[N];
void dfs() {
    for(auto&i: added) i = 0;
    for(int cur = 1; cur <= n; cur ++) {
        for(int i: paths[cur]) {
            int a = 0, b = 0;
            vector<pi> temp;
            temp.reserve(BL);
            while(temp.size() < BL && (a < dp[cur].size() || b < dp[i].size())) {
                if(a == dp[cur].size() || (b < dp[i].size() && dp[cur][a].first + 1 < dp[i][b].first)) {
                    if(!added[dp[i][b].second]) temp.push_back(dp[i][b]);
                    added[dp[i][b].second] = 1;
                    b ++;
                } else {
                    if(!added[dp[cur][a].second]) temp.push_back({dp[cur][a].first + 1, dp[cur][a].second});
                    added[dp[cur][a].second] = 1;
                    a ++;
                }
            }
            for(int j = 0; j < a; j ++) added[dp[cur][j].second] = 0;
            for(int j = 0; j < b; j ++) added[dp[i][j].second] = 0;
            swap(temp, dp[i]);
        }
    }
}
int ANS[N];
bool allowed[N] = {0};
void DP() {
    for(int cur = 1; cur <= n; cur ++) {
        if(ANS[cur] == -1) continue;
        for(int i: paths[cur]) {
            ANS[i] = max(ANS[i], ANS[cur] + 1);
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++) {
        allowed[i] = 1;
        dp[i].reserve(BL);
        dp[i].push_back({0, i});
    }
    while(m--) {
        int a, b;
        cin >> a >> b;
        paths[a].push_back(b);
    }
    dfs();
    while(q--) {
        int a, b;
        cin >> a >> b;
        NOT.resize(b);
        for(auto&i: NOT) {
            cin >> i;
            allowed[i] = 0;
        }
        if(b >= BL) {
            for(int i = 1; i <= n; i ++) {
                if(allowed[i]) ANS[i] = 0;
                else ANS[i] = -1;
            }
            DP();
            cout << ANS[a] << "\n";
        } else {
            bool adde = true;
            for(auto&[v, i]: dp[a]) {
                if(allowed[i]) {
                    adde = false;
                    cout << (v) << "\n";
                    break;
                }
            }
            if(adde) cout << -1 << "\n";
        }
        for(auto&i: NOT) allowed[i] = 1;
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void dfs()':
bitaro.cpp:17:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             while(temp.size() < BL && (a < dp[cur].size() || b < dp[i].size())) {
      |                                        ~~^~~~~~~~~~~~~~~~
bitaro.cpp:17:64: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             while(temp.size() < BL && (a < dp[cur].size() || b < dp[i].size())) {
      |                                                              ~~^~~~~~~~~~~~~~
bitaro.cpp:18:22: 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 |                 if(a == dp[cur].size() || (b < dp[i].size() && dp[cur][a].first + 1 < dp[i][b].first)) {
      |                    ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:18:46: 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 |                 if(a == dp[cur].size() || (b < dp[i].size() && dp[cur][a].first + 1 < dp[i][b].first)) {
      |                                            ~~^~~~~~~~~~~~~~

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