Submission #779250

#	Time	Username	Problem	Language	Result	Execution time	Memory
779250		anhphant	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2073 ms	27404 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void pre_setting() {
    srand(time(NULL));
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    /*#ifndef ONLINE_JUDGE
    freopen("birato.inp", "r", stdin);
    freopen("birato.out", "w", stdout);
    #endif // ONLINE_JUDGE*/
}

namespace subtask2 {
    int N, M, Q, is_visited[100007], longest_path[100007], T, Y, C[100007];
    vector<int> GR[100007], invGR[100007];
    vector<int> topo_order;

    void init() {
        cin >> N >> M >> Q;
        for(int i = 1, s, e; i <= M; i++) {
            cin >> s >> e;
            GR[s].push_back(e);
            invGR[e].push_back(s);
        }
    }

    void topo_dfs(int u) {
        is_visited[u] = 1;
        for(int v : GR[u]) {
            if (!is_visited[v]) topo_dfs(v);
        }
        topo_order.push_back(u);
    }

    void topo_find() {
        for(int i = 1; i <= N; i++)
            if (!is_visited[i]) topo_dfs(i);
        reverse(topo_order.begin(), topo_order.end());

        //for(int u : topo_order) cerr << u << " "; cerr << endl;
    }

    void solve() {
        init();
        topo_find();

        while(Q--) {
            //cerr << "START CASE : " << endl;
            cin >> T >> Y;
            for(int i = 1; i <= Y; i++) cin >> C[i];
            for(int i = 0; i <= N; i++) longest_path[i] = -1e9;
            longest_path[T] = 0;

            for(int i = N - 1; i >= 0; i--) {
                int u = topo_order[i];
                if (longest_path[u] == -1e9) continue;

                for(int v : invGR[u]) {
                    longest_path[v] = max(longest_path[v], longest_path[u] + 1);
                }
            }

            sort(C + 1, C + 1 + Y);
            int ans = -1, idxC = 1;

            for(int i = 1; i <= N; i++) {
                if (idxC <= Y && C[idxC] == i) {
                    idxC++;
                }
                else {
                    ans = max(ans, longest_path[i]);
                    //cerr << i << " " << longest_path[i] << endl;
                }
            }

            cout << ans << endl;
        }
    }
}

namespace subtask3 {
    int N, M, Q, is_visited[100007], longest_path[100007], T, Y, C[100007];
    vector<int> GR[100007], invGR[100007];
    vector<int> topo_order;
    vector<pair<int, int>> vlist[100007];
    const int B = 317;

    void init() {
        cin >> N >> M >> Q;
        for(int i = 1, s, e; i <= M; i++) {
            cin >> s >> e;
            GR[s].push_back(e);
            invGR[e].push_back(s);
        }
    }

    bool added[100007];

    void vlist_construct() {
        for(int i = 1; i <= N; i++) vlist[i].push_back({i, 0});
        for(int u = 1; u <= N; u++) {
            //cerr << u << endl;
            for(int v : GR[u]) {
                vector<pair<int, int>> tmp;
                int pl = 0, pr = 0;
                while(pl < vlist[u].size() || pr < vlist[v].size()) {
                    //cerr << pl << " " << pr << endl;
                    if (pl < vlist[u].size() && vlist[u][pl].second + 1 > vlist[v][pr].second) {
                        if (!added[vlist[u][pl].first])
                            tmp.push_back({vlist[u][pl].first, vlist[u][pl].second + 1});
                        added[vlist[u][pl].first] = 1;
                        pl++;
                    }
                    else {
                        if (!added[vlist[v][pr].first])
                            tmp.push_back(vlist[v][pr]);
                        added[vlist[v][pr].first] = 1;
                        pr++;
                    }
                    if (tmp.size() + 2 == B) break;
                }

                vlist[v] = tmp;
                for(auto [zzz, k] : vlist[v]) added[zzz] = 0;
            }
        }
    }

    void solve() {
        init();
        vlist_construct();

        for(int i = 1; i <= N; i++) {
            sort(vlist[i].begin(), vlist[i].end(), [] (pair<int, int>& x1, pair<int, int>& x2) {
                return x1.second > x2.second;
            });

            /*cerr << "i = " << i << endl;
            for(auto [tt, v] : vlist[i]) cerr << tt << " : " << v << endl;
            cerr << endl;*/
        }

        fill(is_visited + 1, is_visited + 1 + N, 1);

        while(Q--) {
            //cerr << "START CASE" << endl;
            cin >> T >> Y;
            for(int i = 1; i <= Y; i++) {
                cin >> C[i];
                is_visited[C[i]] = 0;
            }

            //cerr << T << endl;
            sort(C + 1, C + 1 + Y);

            if (Y >= B) {
                //cerr << "case 1" << endl;
                for(int i = 1; i <= T; i++) {
                    longest_path[i] = -1e9;
                    if (is_visited[i]) longest_path[i] = max(longest_path[i], 0);
                    if (longest_path[i] == 1e9) continue;
                    for(int v : GR[i]) {
                        longest_path[v] = max(longest_path[v], longest_path[i] + 1);
                    }
                }
                cout << (longest_path[T] < 0? -1 : longest_path[T]) << endl;
            }
            else {
                //cerr << "case 2" << endl;
                for(auto [u, d] : vlist[T]) {
                    //cerr << u << " " << d << endl;
                    if (is_visited[u]) {
                        cout << d << endl;
                        goto GT;
                    }
                }

                cout << -1 << endl;
                GT:
                int hope = -1;
            }

            for(int i = 1; i <= Y; i++) is_visited[C[i]] = 1;
        }
    }
}

int main() {
    pre_setting();
    subtask2 :: solve();
}

Compilation message (stderr)

bitaro.cpp: In function 'void subtask3::vlist_construct()':
bitaro.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 while(pl < vlist[u].size() || pr < vlist[v].size()) {
      |                       ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:108: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]
  108 |                 while(pl < vlist[u].size() || pr < vlist[v].size()) {
      |                                               ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:110:28: 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 |                     if (pl < vlist[u].size() && vlist[u][pl].second + 1 > vlist[v][pr].second) {
      |                         ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void subtask3::solve()':
bitaro.cpp:182:21: warning: unused variable 'hope' [-Wunused-variable]
  182 |                 int hope = -1;
      |                     ^~~~

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