Submission #593150

#	Time	Username	Problem	Language	Result	Execution time	Memory
593150		Do_you_copy	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1292 ms	419916 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];
bool visited[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 (int j: in[i]){
            vector <pii> tem;
            int a = 0, b = 0;
            while (a < top[i].size() && b < top[j].size() && tem.size() < k + 1){
                if (top[i][a].fi > top[j][b].fi + 1){
                    tem.pb(top[i][a]);
                    visited[top[i][a].se] = 1;
                    ++a;
                }
                else{
                    tem.pb({top[j][b].fi + 1, top[j][b].se});
                    visited[top[j][b].se] = 1;
                    ++b;
                }
                while(a < top[i].size() && visited[top[i][a].se]) ++a;
                while(b < top[j].size() && visited[top[j][b].se]) ++b;
            }
            while (tem.size() < k + 1 && a < top[i].size()){
                tem.pb(top[i][a]);
                visited[top[i][a].se] = 1;
                ++a;
                while(a < top[i].size() && visited[top[i][a].se]) ++a;
            }
            while (tem.size() < k + 1 && b < top[j].size()){
                tem.pb({top[j][b].fi + 1, top[j][b].se});
                visited[top[j][b].se] = 1;
                ++b;
                while(b < top[j].size() && visited[top[j][b].se]) ++b;
            }
            swap(top[i], tem);
            for (pii j: top[i]) visited[j.se] = 0;
        }
        //cerr << i << "\n";
        //for (pii j: top[i]) cerr << j.fi << " " << j.se << "\n";
    }
    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:56: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]
   56 |         for (int i = 0; i < top[t].size(); ++i){
      |                         ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'void Init()':
bitaro.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             while (a < top[i].size() && b < top[j].size() && tem.size() < k + 1){
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:84:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             while (a < top[i].size() && b < top[j].size() && tem.size() < k + 1){
      |                                         ~~^~~~~~~~~~~~~~~
bitaro.cpp:84:73: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |             while (a < top[i].size() && b < top[j].size() && tem.size() < k + 1){
      |                                                              ~~~~~~~~~~~^~~~~~~
bitaro.cpp:95: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]
   95 |                 while(a < top[i].size() && visited[top[i][a].se]) ++a;
      |                       ~~^~~~~~~~~~~~~~~
bitaro.cpp:96: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]
   96 |                 while(b < top[j].size() && visited[top[j][b].se]) ++b;
      |                       ~~^~~~~~~~~~~~~~~
bitaro.cpp:98:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |             while (tem.size() < k + 1 && a < top[i].size()){
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:98:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while (tem.size() < k + 1 && a < top[i].size()){
      |                                          ~~^~~~~~~~~~~~~~~
bitaro.cpp:102: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]
  102 |                 while(a < top[i].size() && visited[top[i][a].se]) ++a;
      |                       ~~^~~~~~~~~~~~~~~
bitaro.cpp:104:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |             while (tem.size() < k + 1 && b < top[j].size()){
      |                    ~~~~~~~~~~~^~~~~~~
bitaro.cpp:104:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             while (tem.size() < k + 1 && b < top[j].size()){
      |                                          ~~^~~~~~~~~~~~~~~
bitaro.cpp:108: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]
  108 |                 while(b < top[j].size() && visited[top[j][b].se]) ++b;
      |                       ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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