Submission #860682

#	Time	Username	Problem	Language	Result	Execution time	Memory
860682		clams	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	919 ms	289036 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

template <typename T>
bool maxi(T& a, T b) {
    if (b > a) return a = b, true;
    return false;
}

template <typename T>
bool mini(T& a, T b) {
    if (b < a) return a = b, true;
    return false;
}

string to_string(string s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int Q = 1e5 + 5;
const int B = 350;

int n, m, q;
vector<int> radj[N];

int t, y;
int c[N];
bool ded[N];

int vis[N];
int len[N]; // len[u] = current length of path starting from u
vector<pair<int, int>> best[N]; // B best paths ends at u

void pre() {
    for (int i = 1; i <= n; i++) {
        vector<int> uniq;
        for (int v : radj[i]) {
            for (pair<int, int> p : best[v]) {
                int u = p.second, l = p.first;
                if (vis[u] != i) {
                    vis[u] = i;
                    uniq.push_back(u);
                    len[u] = l + 1;
                } else {
                    maxi(len[u], l + 1);
                }
            }
        }
        uniq.push_back(i);
        sort(all(uniq), [&](int u, int v) {
            return len[u] > len[v]; 
        });
        best[i].resize(min(B, sz(uniq)));
        for (int j = 0; j < sz(best[i]); j++) best[i][j] = make_pair(len[uniq[j]], uniq[j]);
        debug(i, best[i]);
    }
}

void hard() {
    int ans = -1;
    for (pair<int, int> p : best[t]) {
        int u = p.second, l = p.first;
        if (!ded[u]) {
            ans = l;
            break;
        }
    }
    cout << ans << '\n';
}

int f[N];
void easy() {
    memset(f, -1, sizeof f);
    f[t] = 0;
    int ans = -1;
    for (int i = t; i >= 1; i--) {
        if (f[i] == -1) continue;
        if (!ded[i]) maxi(ans, f[i]);
        for (int v : radj[i]) {
            maxi(f[v], f[i] + 1);
        }
    }
    cout << ans << '\n';
}

void solve() {
    cin >> t >> y;
    for (int i = 1; i <= y; i++) {
        cin >> c[i];
        ded[c[i]] = 1;
    }
    if (y > B) easy();
    else hard();
}

void clean() {
    for (int i = 1; i <= y; i++) {
        ded[c[i]] = 0;
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int s, e;
        cin >> s >> e;
        radj[e].push_back(s);
    }
    pre();
    while (q--) {
        solve();
        clean();
    }
}

/*
https://oj.uz/problem/view/JOI18_bitaro
*/

Compilation message (stderr)

bitaro.cpp: In function 'void pre()':
bitaro.cpp:63:20: warning: statement has no effect [-Wunused-value]
   63 | #define debug(...) 42
      |                    ^~
bitaro.cpp:103:9: note: in expansion of macro 'debug'
  103 |         debug(i, best[i]);
      |         ^~~~~

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