Submission #859733

#	Time	Username	Problem	Language	Result	Execution time	Memory
859733		GenghizKhan	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1088 ms	271160 KiB

bitaro

// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include "complex"

using namespace std;
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
// #define int long long
typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define si(n) scanf("%d", &n)
#define dout(n) printf("%d\n", n)
#define sll(n) scanf("%lld", &n)
#define lldout(n) printf("%lld\n", n)
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define endl "\n"
const long long mod = 1e9 + 7;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt(seed);  // use mt()%mod
void prec() {
}
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> graph[n], revadj[n];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].PB(v);
        revadj[v].PB(u);
    }
    int bucket_sz = sqrt(n);
    vector<vector<pair<int, int>>> best(n);
    vector<bool> picked(n, false);
    for (int i = 0; i < n; i++) {
        int v = i;
        for (auto u : revadj[v]) {
            if (!best[v].size()) {
                best[v] = best[u];
            } else {
                vector<pair<int, int>> new_best;
                int p1 = 0, p2 = 0;

                while (p1 < best[v].size() && p2 < best[u].size() && new_best.size() < bucket_sz) {
                    if (picked[best[v][p1].first]) {
                        p1++;
                        continue;
                    }
                    if (picked[best[u][p2].first]) {
                        p2++;
                        continue;
                    }
                    if (best[v][p1].second >= best[u][p2].second) {
                        new_best.PB(best[v][p1]);
                        p1++;
                    } else {
                        new_best.PB(best[u][p2]);
                        p2++;
                    }
                    picked[new_best.back().first] = true;
                }
                while (p1 < best[v].size() && new_best.size() < bucket_sz) {
                    if (picked[best[v][p1].first]) {
                        p1++;
                        continue;
                    }
                    new_best.PB(best[v][p1]);
                    picked[new_best.back().first] = true;
                    p1++;
                }
                while (p2 < best[u].size() && new_best.size() < bucket_sz) {
                    if (picked[best[u][p2].first]) {
                        p2++;
                        continue;
                    }
                    new_best.PB(best[u][p2]);
                    picked[new_best.back().first] = true;
                    p2++;
                }
                best[v] = new_best;
                for (auto z : best[v]) picked[z.first] = false;
            }
        }
        if (best[v].size() < bucket_sz) {
            best[v].PB({v, -1});
        }
        for (int j = 0; j < best[v].size(); j++) {
            best[v][j].second++;
        }
        // for (int j = 0; j < best[i].size(); j++) {
        //     cout << i << ": " << best[i][j].first << " " << best[i][j].second << endl;
        // }
    }
    vector<int> dist(n);
    unordered_map<int, bool> mm;
    while (q--) {
        int town;
        cin >> town;
        town--;
        int ct;
        cin >> ct;
        vector<int> busy(ct);
        for (int i = 0; i < ct; i++) {
            cin >> busy[i];
            busy[i]--;
            mm[busy[i]] = true;
        }
        if (ct >= bucket_sz) {
            dist = vector<int>(n, -1);
            dist[town] = 0;
            for (int i = n - 1; i >= 0; i--) {
                int v = i;
                if (dist[v] == 0) continue;
                int maxi = -1;
                for (auto u : graph[v]) {
                    if (dist[u] != -1) maxi = max(maxi, dist[u] + 1);
                }
                if (maxi != -1) dist[v] = maxi;
            }
            int max_dist = -1;
            for (int i = 0; i < n; i++) {
                if (dist[i] == -1 || mm[i]) continue;
                if (dist[i] > max_dist)
                    max_dist = dist[i];
            }
            cout << max_dist << endl;

        } else {
            int max_dist = -1;
            for (int i = 0; i < best[town].size(); i++) {
                int v = best[town][i].first;
                if (mm[v]) continue;
                max_dist = best[town][i].second;
                break;
            }
            cout << max_dist << endl;
        }
        for (int i = 0; i < busy.size(); i++) {
            mm[busy[i]] = false;
        }
    }
}

signed main() {
    fast_io;
    prec();
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    int totalTests = 1;
    // cin >> totalTests / ;
    for (int testNo = 1; testNo <= totalTests; testNo++) {
        // cout << "Case #" << testNo << ": ";
        solve();
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:67: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]
   67 |                 while (p1 < best[v].size() && p2 < best[u].size() && new_best.size() < bucket_sz) {
      |                        ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:67:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 while (p1 < best[v].size() && p2 < best[u].size() && new_best.size() < bucket_sz) {
      |                                               ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:67:86: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |                 while (p1 < best[v].size() && p2 < best[u].size() && new_best.size() < bucket_sz) {
      |                                                                      ~~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:85: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]
   85 |                 while (p1 < best[v].size() && new_best.size() < bucket_sz) {
      |                        ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:85:63: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |                 while (p1 < best[v].size() && new_best.size() < bucket_sz) {
      |                                               ~~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:94: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]
   94 |                 while (p2 < best[u].size() && new_best.size() < bucket_sz) {
      |                        ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:94:63: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |                 while (p2 < best[u].size() && new_best.size() < bucket_sz) {
      |                                               ~~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:107:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |         if (best[v].size() < bucket_sz) {
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~~
bitaro.cpp:110: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]
  110 |         for (int j = 0; j < best[v].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~
bitaro.cpp:153: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]
  153 |             for (int i = 0; i < best[town].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int i = 0; i < busy.size(); i++) {
      |                         ~~^~~~~~~~~~~~~

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