Submission #829411

#	Time	Username	Problem	Language	Result	Execution time	Memory
829411		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1273 ms	504364 KiB

bitaro

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 100100;
const int SQ = 300;

vector < int > adj[N], dp(N), use(N);
vector < pair < int, int > > calc[N];
queue < pair < int, int > > q;

int True;

void merge(int a, int b) {
    ++ True;
    for(int i = 0, j = 0; q.size() < SQ;) {
        for(; i < calc[a].size() && use[calc[a][i].first] == True; ++ i);
        for(; j < calc[b].size() && use[calc[b][j].first] == True; ++ j);
        if(i == calc[a].size() && j == calc[b].size()) {
            break;
        }
        if(j == calc[b].size() || (i != calc[a].size() && calc[b][j].second < calc[a][i].second)) {
            q.push(calc[a][i]);
            use[calc[a][i].first] = True;
            ++ i;
        } else {
            ++ calc[b][j].second;
            q.push(calc[b][j]);
            -- calc[b][j].second;
            use[calc[b][j].first] = True;
            ++ j;
        }
    }
    calc[a].resize(q.size());
    for(int i = 0; i < calc[a].size(); ++ i) {
        calc[a][i] = q.front();
        q.pop();
    }
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, Q, u, v;
    for(cin >> n >> m >> Q; m --> 0;) {
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for(int i = 1; i <= n; ++ i) {
        calc[i].push_back({i, 0});
        for(auto &j : adj[i]) {
            merge(j, i);
        }
    }
    /**
    for(int i = 1; i <= n; ++ i) {
        cout << i << "\n";
        for(auto &[from, dist] : calc[i]) {
            cout << from << " ---- " << dist << '\n';
        }
        cout << "\n\n\n";
    }
    // */
    for(int T, Y, C, tt; Q --> 0;) {
        ++ True;
        for(cin >> T >> Y, tt = Y; tt --> 0;) {
            cin >> C;
            use[C] = True;
        }
        if(Y < SQ) {
            int i = 0;
            for(; i < calc[T].size() && use[calc[T][i].first] == True; ++ i);
            cout << (i == calc[T].size() ? -1 : calc[T][i].second) << '\n';
        } else {
            for(int i = 0; i < n; dp[++ i] = -1);
            for(int i = 1; i <= n; ++ i) {
                dp[i] += use[i] != True || dp[i] != -1;
                for(auto &j : adj[i]) {
                    dp[j] = max(dp[j], dp[i]);
                }
            }
            cout << dp[T] << '\n';
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int, int)':
bitaro.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(; i < calc[a].size() && use[calc[a][i].first] == True; ++ i);
      |               ~~^~~~~~~~~~~~~~~~
bitaro.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(; j < calc[b].size() && use[calc[b][j].first] == True; ++ j);
      |               ~~^~~~~~~~~~~~~~~~
bitaro.cpp:26:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(i == calc[a].size() && j == calc[b].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:26:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(i == calc[a].size() && j == calc[b].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(j == calc[b].size() || (i != calc[a].size() && calc[b][j].second < calc[a][i].second)) {
      |            ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:29:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(j == calc[b].size() || (i != calc[a].size() && calc[b][j].second < calc[a][i].second)) {
      |                                    ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:42: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]
   42 |     for(int i = 0; i < calc[a].size(); ++ i) {
      |                    ~~^~~~~~~~~~~~~~~~
bitaro.cpp: At global scope:
bitaro.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(; i < calc[T].size() && use[calc[T][i].first] == True; ++ i);
      |                   ~~^~~~~~~~~~~~~~~~
bitaro.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             cout << (i == calc[T].size() ? -1 : calc[T][i].second) << '\n';
      |                      ~~^~~~~~~~~~~~~~~~~

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