Submission #670455

#	Time	Username	Problem	Language	Result	Execution time	Memory
670455		hafo	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1500 ms	414468 KiB

bitaro

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const int oo = 1e9 + 69;
const int sz = 320;

int n, m, q, u, v, t, y, c, id[maxn], d[maxn];
bool vis[maxn];
vector<pa> f[maxn];
vector<int> arc[maxn];

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

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m>>q;
    while(m--) {
        cin>>u>>v;
        arc[v].pb(u);
    }

    for(auto v = 1; v <= n; v++) {
        for(auto u:arc[v]) {
            vector<pa> cur;
            f[u].pb(make_pair(0, u));
            int i = 0, j = 0;
            while(cur.size() < sz && (i < f[u].size() || j < f[v].size())) {
                if(j == f[v].size() || (i < f[u].size() && f[u][i].fi + 1 >= f[v][j].fi)) {
                    cur.pb(make_pair(f[u][i].fi + 1, f[u][i].se));
                    vis[cur.back().se] = 1;
                } else {
                    cur.pb(f[v][j]);
                    vis[cur.back().se] = 1;
                }

                while(i < f[u].size() && vis[f[u][i].se]) i++;
                while(j < f[v].size() && vis[f[v][j].se]) j++;
            }
            f[u].pop_back();
            for(auto i:cur) vis[i.se] = 0;
            swap(f[v], cur);
        }
    }

    fill_n(id, n + 1, 0);
    for(int k = 1; k <= q; k++) {
        cin>>t>>y;
        for(int i = 0; i < y; i++) {
            cin>>c;
            id[c] = k;
        }

        if(y >= sz) {
            fill_n(d, n + 1, -1);
            d[t] = 0;
            int ans = -1;
            if(id[t] != k) ans = 0;
            bool ok = 0;

            for(int u = t; u >= 1; u--) {
                if(d[u] == -1) continue;
                for(auto v:arc[u]) {
                    maxi(d[v], d[u] + 1);
                    if(id[v] != k) maxi(ans, d[v]);
                }
            }
            cout<<ans<<"\n";
        } else {
            int ans = -1;
            if(id[t] != k) maxi(ans, 0);
            for(auto i:f[t])
                if(id[i.se] != k) maxi(ans, i.fi);
            cout<<ans<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:45:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             while(cur.size() < sz && (i < f[u].size() || j < f[v].size())) {
      |                                       ~~^~~~~~~~~~~~~
bitaro.cpp:45:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             while(cur.size() < sz && (i < f[u].size() || j < f[v].size())) {
      |                                                          ~~^~~~~~~~~~~~~
bitaro.cpp:46: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]
   46 |                 if(j == f[v].size() || (i < f[u].size() && f[u][i].fi + 1 >= f[v][j].fi)) {
      |                    ~~^~~~~~~~~~~~~~
bitaro.cpp:46: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]
   46 |                 if(j == f[v].size() || (i < f[u].size() && f[u][i].fi + 1 >= f[v][j].fi)) {
      |                                         ~~^~~~~~~~~~~~~
bitaro.cpp:54: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]
   54 |                 while(i < f[u].size() && vis[f[u][i].se]) i++;
      |                       ~~^~~~~~~~~~~~~
bitaro.cpp:55: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]
   55 |                 while(j < f[v].size() && vis[f[v][j].se]) j++;
      |                       ~~^~~~~~~~~~~~~
bitaro.cpp:76:18: warning: unused variable 'ok' [-Wunused-variable]
   76 |             bool ok = 0;
      |                  ^~

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