Submission #669857

#	Time	Username	Problem	Language	Result	Execution time	Memory
669857		hafo	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2060 ms	13308 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 ll oo = 1e15 + 69;
const int sz = 320;

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

void dfs(int u) {
    vis[u] = 1;
    for(auto v:g[u])
        if(!vis[v]) dfs(v);
    topo.pb(u);
}

int bs(int x, int u) {
    int l = 0, r = sz - 1, mid, res = -1;
    while(l <= r) {
        mid = l + r >> 1;
        if(f[mid][u].fi < x) {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    return res;
}

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;
        g[u].pb(v);
        arc[v].pb(u);
    }

    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i);
    reverse(all(topo));

    for(int i = 1; i <= n; i++)
    for(int j = 0; j < sz; j++) f[j][i] = {0, (j == 0 ? i:-1)};
    for(auto u:topo) {
        for(int k = 0; k < sz; k++) {
            if(f[k][u].se == -1) continue;
            for(auto v:g[u]) {
                int i = bs(f[k][u].fi + 1, v);
                if(i == -1) continue;
                for(int j = max(sz - 1, bs(1, v) + 1); j > i; j--) f[j][v] = f[j - 1][v];
                f[i][v] = {f[k][u].fi + 1, f[k][u].se};
            }
        }
    }

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

Compilation message (stderr)

bitaro.cpp: In function 'int bs(int, int)':
bitaro.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         mid = l + r >> 1;
      |               ~~^~~

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