Submission #1066153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066153		baotoan655	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	512 ms	146260 KiB

bitaro

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REV(i, b, a) for(int i = (b); i >= (a); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define ll long long
#define fi first
#define se second
using namespace std;

const int N = 1e5 + 5;
int n, m, q;
vector<int> rg[N];
int block;
bool blocked[N];
vector<pair<int, int>> pre[N];
int dp[N];
int from[N];

void solve(int tc) {
    cin >> n >> m >> q;
    block = 100;
    REP(_, m) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        rg[v].emplace_back(u);
    }
    memset(from, -1, sizeof from);
    REP(i, n) {
        pre[i].emplace_back(0, i);
        vector<int> from_i;
        for(int _ = 0; _ < rg[i].size(); ++_) {
            int j = rg[i][_];
            for(int __ = 0; __ < pre[j].size(); ++__) {
                int dist = pre[j][__].fi, idx = pre[j][__].se;
                if(from[idx] == -1) {
                    from_i.emplace_back(idx);
                    from[idx] = dist + 1;
                } else {
                    from[idx] = max(from[idx], dist + 1);
                }
            }
        }
        for(int _ = 0; _ < from_i.size(); ++_) {
            int j = from_i[_];
            pre[i].emplace_back(from[j], j);
        }
        sort(pre[i].begin(), pre[i].end(), greater<pair<int, int>>());
        while(pre[i].size() > block) pre[i].pop_back();
        for(int _ = 0; _ < from_i.size(); ++_) {
            int j = from_i[_];
            from[j] = -1;
        }
    }
    REP(_, q) {
        int t, y;
        cin >> t >> y;
        --t;
        vector<int> ve(y);
        REP(i, y) {
            cin >> ve[i];
            --ve[i];
            blocked[ve[i]] = true;
        }
        int ans = -1;
        if(y >= block) {
            for(int i = 0; i <= t; ++i) dp[i] = -1;
            dp[t] = 0;
            for(int i = t; i >= 0; --i) {
                if(dp[i] == -1) continue;
                if(!blocked[i]) ans = max(ans, dp[i]);
                for(int _ = 0; _ < rg[i].size(); ++_) {
                    int j = rg[i][_];
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        } else {
            for(int i = 0; i < (int)pre[t].size(); ++i) {
                if(!blocked[pre[t][i].se]) {
                    ans = pre[t][i].fi;
                    break;
                }
            }
        }
        cout << ans << '\n';

        for(int i = 0; i < (int)ve.size(); ++i) {
            blocked[ve[i]] = false;
        }
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    for(int i = 1; i <= tc; ++i) solve(tc);
    return (0);
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve(int)':
bitaro.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int _ = 0; _ < rg[i].size(); ++_) {
      |                        ~~^~~~~~~~~~~~~~
bitaro.cpp:35:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int __ = 0; __ < pre[j].size(); ++__) {
      |                             ~~~^~~~~~~~~~~~~~~
bitaro.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int _ = 0; _ < from_i.size(); ++_) {
      |                        ~~^~~~~~~~~~~~~~~
bitaro.cpp:50:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         while(pre[i].size() > block) pre[i].pop_back();
      |               ~~~~~~~~~~~~~~^~~~~~~
bitaro.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int _ = 0; _ < from_i.size(); ++_) {
      |                        ~~^~~~~~~~~~~~~~~
bitaro.cpp:73:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for(int _ = 0; _ < rg[i].size(); ++_) {
      |                                ~~^~~~~~~~~~~~~~

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