Submission #593030

#	Time	Username	Problem	Language	Result	Execution time	Memory
593030		Do_you_copy	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2099 ms	215284 KiB

bitaro

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;

int n, m, q, k = 350;
vector <int> out[maxN], in[maxN];
vector <pii> top[maxN];
bool cant[maxN];
int dp[maxN];

void query(){
    int t, y; cin >> t >> y;
    vector <int> c(y);
    for (int i = 0; i < y; ++i){
        cin >> c[i];
        cant[c[i]] = 1;
    }
    if (y > k){
        fill(dp + 1, dp + n + 1, -1);
        for (int i = 1; i <= t; ++i){
            if (!cant[i]) dp[i] = 0;
            for (int j: in[i]){
                if (dp[j] != -1)
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        cout << dp[t] << "\n";
        goto clearr;
    }
    else{
        for (int i = 0; i < top[t].size(); ++i){
            if (!cant[top[t][i].se]){
                cout << top[t][i].fi << "\n";
                goto clearr;
            }
        }
        cout << -1 << "\n";
        goto clearr;
    }
clearr:
    for (int i: c){
        cant[i] = 0;
    }
}

void Init(){
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        in[v].pb(u);
        out[u].pb(v);
    }
    for (int i = 1; i <= n; ++i){
        top[i].pb({0, i});
        for (const int &j: in[i]){
            for (const pii &l: top[j]){
                top[i].pb({l.fi + 1, l.se});
            }
        }
        sort(top[i].begin(), top[i].end(),[](const auto &l, const auto &r){
            if (l.se == r.se) return l.fi > r.fi;
            return l.se < r.se;
        });
        top[i].resize(unique(top[i].begin(), top[i].end(),[](const auto &l, const auto &r){
            return l.se == r.se;
        }) - top[i].begin());
        sort(top[i].begin(), top[i].end(), greater<pii>());
        if (top[i].size() > k + 1){
            top[i].resize(k + 1);
        }
    }
    while (q--){
        query();
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void query()':
bitaro.cpp:55: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]
   55 |         for (int i = 0; i < top[t].size(); ++i){
      |                         ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'void Init()':
bitaro.cpp:93:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |         if (top[i].size() > k + 1){
      |             ~~~~~~~~~~~~~~^~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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