제출 #382254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382254		maksim1744	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1784 ms	421384 KiB

bitaro

/*
    author:  Maksim1744
    created: 26.03.2021 23:25:44
*/

#include "bits/stdc++.h"

using namespace std;

#define ll   long long
#define ld   long double

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T>& v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T>& v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T>& v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "C:/C++ libs/print.cpp"
#else
#define show(...)     42
#define mclock        42
#define shows         42
#define debug if (false)
#endif

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;
    const int B = 450;
    vector<vector<int>> g(n), gi(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].pb(b);
        gi[b].pb(a);
    }

    vector<int> ui(n, -1);
    int ustep = 0;

    auto mrg = [&](vector<pair<int, int>> &a, vector<pair<int, int>> b) {
        ++ustep;
        int ia = 0, ib = 0;
        for (int i = 0; i < b.size(); ++i) {
            b[i].first++;
        }
        vector<pair<int, int>> res;
        while ((ia < a.size() || ib < b.size()) && res.size() < B) {
            bool cha;
            if (ia == a.size()) cha = false;
            else if (ib == b.size()) cha = true;
            else if (a[ia].first > b[ib].first) cha = true;
            else cha = false;

            if (cha) {
                if (ui[a[ia].second] != ustep)
                    res.pb(a[ia]);
                ui[a[ia].second] = ustep;
                ++ia;
            } else {
                if (ui[b[ib].second] != ustep)
                    res.pb(b[ib]);
                ui[b[ib].second] = ustep;
                ++ib;
            }
        }
        show(a, b, res);
        return res;
    };

    vector<bool> u(n, false);
    vector<vector<pair<int, int>>> dp(n);
    vector<int> order;
    function<void(int)> dfs1 = [&](int v) {
        u[v] = true;
        dp[v].eb(0, v);
        for (int k : gi[v]) {
            if (!u[k]) {
                dfs1(k);
            }
            dp[v] = mrg(dp[v], dp[k]);
        }
        order.pb(v);
    };
    for (int i = 0; i < n; ++i) {
        if (!u[i])
            dfs1(i);
    }

    show(gi);

    show(dp);
    vector<int> dist(n);
    show(g);
    reverse(order.begin(), order.end());

    while (q--) {
        int v, y;
        cin >> v >> y;
        --v;

        ++ustep;
        for (int i = 0; i < y; ++i) {
            int k;
            cin >> k;
            --k;
            ui[k] = ustep;
        }

        if (y < B) {
            int ans = -1;
            for (auto [a, b] : dp[v]) {
                if (ui[b] != ustep) {
                    ans = a;
                    break;
                }
            }
            cout << ans << '\n';
        } else {
            int ans = -1;
            dist.assign(n, -1e9);
            show(order);
            show(v);
            dist[v] = 0;
            for (int k : order) {
                for (int u : g[k])
                    dist[k] = max(dist[k], dist[u] + 1);
                if (ui[k] != ustep)
                    ans = max(ans, dist[k]);
            }
            show(dist);
            cout << ans << '\n';
        }
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In lambda function:
bitaro.cpp:69: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]
   69 |         for (int i = 0; i < b.size(); ++i) {
      |                         ~~^~~~~~~~~~
bitaro.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while ((ia < a.size() || ib < b.size()) && res.size() < B) {
      |                 ~~~^~~~~~~~~~
bitaro.cpp:73: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]
   73 |         while ((ia < a.size() || ib < b.size()) && res.size() < B) {
      |                                  ~~~^~~~~~~~~~
bitaro.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             if (ia == a.size()) cha = false;
      |                 ~~~^~~~~~~~~~~
bitaro.cpp:76:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             else if (ib == b.size()) cha = true;
      |                      ~~~^~~~~~~~~~~
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:92:9: note: in expansion of macro 'show'
   92 |         show(a, b, res);
      |         ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:115:5: note: in expansion of macro 'show'
  115 |     show(gi);
      |     ^~~~
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:117:5: note: in expansion of macro 'show'
  117 |     show(dp);
      |     ^~~~
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:119:5: note: in expansion of macro 'show'
  119 |     show(g);
      |     ^~~~
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:147:13: note: in expansion of macro 'show'
  147 |             show(order);
      |             ^~~~
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:148:13: note: in expansion of macro 'show'
  148 |             show(v);
      |             ^~~~
bitaro.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
bitaro.cpp:156:13: note: in expansion of macro 'show'
  156 |             show(dist);
      |             ^~~~

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