제출 #334783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334783		trthminh	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	6 ms	5612 KiB

bitaro

#include <bits/stdc++.h>
#define task "Bitaro"
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define ll long long
using namespace std;
typedef pair < int, int > ii;
const int N = 1e5 + 2, can = 200;
int n, m, q, na, mx[N], dp[N];
ii a[N];
bool busy[N];
vector < int > g[N];
vector < ii > data[N];
bool cmp(ii x, ii y)
{
    return x.F > y.F;
}
void pre()
{
    rep(i, 1, n)
    {
        vector < int > tmp;
        for (int v : g[i])
        {
            if (!mx[v])
                tmp.eb(v);
            mx[v] = max(mx[v], 1);
            for (ii it : data[v])
            {
                if (!mx[it.S])
                    tmp.eb(it.S);
                mx[it.S] = max(mx[it.S], it.F + 1);
            }
        }
        if (tmp.size() < can)
            tmp.eb(i);
        int na = 0;
        for (int v : tmp)
            a[++na] = {mx[v], v}, mx[v] = 0;
        nth_element(a + 1, a + 1 + min(can, na), a + 1 + na, cmp);
        rep(j, 0, min(na, can) - 1)
            data[i].eb(a[j+1]);
    }
}
int solve(int s)
{
    int res = -1;
    fill(dp+1, dp+1+n, INT_MIN);
    dp[s] = 0;
    for (int i = s - 1; i >= 1; --i)
        for (int j : g[i])
            dp[j] = max (dp[j], dp[i] + 1);
    for (int i = 1; i <= s; ++i)
        res = max (res, dp[i]);
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> q;
    rep(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        g[v].eb(u);
    }
    pre();
    while (q--)
    {
        int s, num;
        cin >> s >> num;
        vector < int > tmp;
        rep(i, 0, num - 1)
        {
            int x;
            cin >> x;
            busy[x] = 1;
            tmp.eb(x);
        }
        if (num >= can) cout << solve(s) << '\n';
        else
        {
            int res = -1;
            for (ii it : data[s])
                if (!busy[it.S])
                    res = max(res, it.F);
            cout << res << '\n';
        }
        for (auto i : tmp)
            busy[i] = 0;
    }
    return 0;
}

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