| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839262 | serifefedartar | Bitaro’s Party (JOI18_bitaro) | C++17 | 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 debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 15
#define MAXN 100005
const int SQRT = 300;
vector<vector<int>> graph, rev;
vector<vector<pair<int,int>>> dist;
bool closed[MAXN];
void get(int to, int from) {
vector<pair<int,int>> new_l;
int l = 0;
int sz = dist[to].size();
for (auto u : dist[from]) {
while (l < sz && dist[to][l].f < u.f) {
new_l.push_back(dist[to][l]);
l++;
}
new_l.push_back({u.f, u.s+1});
if (l < sz && dist[to][l].f == new_l.back().f && dist[to][l].s > new_l.back().s) {
new_l.pop_back();
new_l.push_back({u.f, dist[to][l].s});
l++;
}
if (l < sz && dist[to][l].f == new_l.back().f)
l++;
}
sort(new_l.begin(), new_l.end(), [&](pair<int,int> &a, pair<int,int> &b) {
return a.s > b.s;
});
new_l.resize(min(new_l.size(), SQRT));
sort(new_l.begin(), new_l.end());
dist[to] = new_l;
}
int main() {
fast
int N, M, Q, S, E;
cin >> N >> M >> Q;
graph = vector<vector<int>>(N+1, vector<int>());
rev = vector<vector<int>>(N+1, vector<int>());
dist = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
for (int i = 0; i < M; i++) {
cin >> S >> E;
graph[S].push_back(E);
rev[E].push_back(S);
}
for (int i = 1; i <= N; i++) {
dist[i].push_back({i, 0});
for (auto u : graph[i])
get(u, i);
}
while (Q--) {
int town, cnt;
cin >> town >> cnt;
vector<int> towns(cnt);
for (int i = 0; i < cnt; i++) {
cin >> towns[i];
closed[towns[i]] = true;
}
int ans = -1;
if (cnt >= SQRT) {
vector<int> new_dist(N+1, -1e8);
new_dist[town] = 0;
for (int i = town; i >= 1; i--) {
if (new_dist[i] < 0)
continue ;
for (auto u : rev[i])
new_dist[u] = max(new_dist[u], new_dist[i] + 1);
}
for (int i = 1; i <= town; i++) {
if (!closed[i])
ans = max(ans, new_dist[i]);
}
} else {
for (auto u : dist[town]) {
if (!closed[u.f])
ans = max(ans, u.s);
}
}
cout << ans << "\n";
for (auto u : towns)
closed[u] = false;
}
}