| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 334475 | trthminh | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define req(i, a, b) for(ll i = (a); i >= (b); --i)
#define name "bitaro"
#define pb emplace_back
#define sz size()
#define ff first
#define ss second
typedef pair < int, int > ii;
const int maxn = 1e5 + 7, oo = 1e9, mod = 1e9 + 7, can = 100;
int n, m, q, x, y, busy[maxn], b[maxn], s, cnt, f[maxn];
vector < int > a[maxn], aa[maxn];
vector < ii > furthest[maxn];
void pre()
{
rep (i, 1, n)
{
vector < ii > tmp;
for (int j : a[i])
for (auto k : furthest[j])
tmp.pb({k.ff + 1, k.ss});
tmp.pb({0, i});
sort(tmp.begin(), tmp.end(), greater < ii > ());
for (auto j : tmp)
{
if (busy[j.ss] == 0)
{
busy[j.ss] = 1;
furthest[i].pb(j);
if (furthest[i].sz == can)
break;
}
}
for (auto j : furthest[i])
busy[j.ss] = 0;
}
}
void solve2()
{
int res = -1;
for (auto i : furthest[s])
if (!busy[i.ss])
res = max (res, i.ff);
cout << res << '\n';
}
void solve1()
{
rep (i, 1, n)
f[i] = -oo;
f[s] = 0;
for (int i = s - 1; i >= 1; --i)
for (int j : aa[i])
f[i] = max (f[i], f[j] + 1);
int res = -1;
rep (i, 1, s)
if (!busy[i])
res = max (res, f[i]);
cout << res << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
cin >> n >> m >> q;
rep (i, 1, m)
{
cin >> x >> y;
a[y].pb(x);
aa[x].pb(y);
}
pre();
while (q--)
{
cin >> s >> cnt;
rep (i, 1, cnt)
{
cin >> b[i];
busy[b[i]] = 1;
}
if (cnt >= can)
solve1();
else solve2();
rep (i, 1, cnt)
busy[b[i]] = 0;
}
}