# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
521179 | Ai7081 | Bitaro’s Party (JOI18_bitaro) | C++17 | 6 ms | 10060 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;
const int N = 100005;
struct Query{
int town, idx;
vector<int> busy;
bool operator < (const Query &o) const { return town < o.town; }
};
int out[N];
set<pair<int, int>, greater<pair<int, int>>> s[N];
set<int, greater<int>> rev[N];
vector<Query> que;
bool mark[N], isbusy[N];
int dfs(int v) {
int ret = 0;
mark[v] = true;
for (auto to : rev[v]) {
if (!mark[to] && !(isbusy[to] && rev[to].empty())) ret = max(ret, dfs(to) + 1);
}
return ret;
}
int main() {
int n, m, Q, a, b, n_busy;
scanf(" %d %d %d", &n, &m, &Q);
int sq = ceil(sqrt(n+.0));
while (m--) {
scanf(" %d %d", &a, &b);
rev[max(a, b)].insert(min(a, b));
}
for (int i=1; i<=Q; i++) {
Query in;
in.idx = i;
scanf(" %d %d", &in.town, &n_busy);
while (n_busy--) {
scanf(" %d", &a);
in.busy.push_back(a);
}
que.push_back(in);
}
sort(que.begin(), que.end());
int now = 1;
for (int i=1; i<=n; i++) s[i].insert({0, i});
fill_n(out, n+5, -1);
for (auto q : que) {
while (now < q.town) {
now++;
for (auto to : rev[now]) {
for (auto [val, from] : s[to]) {
if (s[now].size() < sq) s[now].insert({val+1, from});
else if (val+1 > (--s[now].end())->first) {
s[now].erase(--s[now].end());
s[now].insert({val+1, from});
}
}
}
}
if (q.busy.size() >= sq) {
fill_n(mark, n+5, false);
fill_n(isbusy, n+5, false);
for (auto it : q.busy) isbusy[it] = true;
out[q.idx] = dfs(q.town);
if (!out[q.idx] && isbusy[q.town]) out[q.idx] = -1;
}
else {
for (auto [val, from] : s[now]) {
auto tmp = lower_bound(q.busy.begin(), q.busy.end(), from);
if (tmp == q.busy.end() || *tmp != from) {
out[q.idx] = val;
break;
}
}
}
}
for (int i=1; i<=Q; i++) printf("%d\n", out[i]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |