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>
#define pb push_back
#define f first
#define s second
using namespace std;
const int N = 1e5 + 5;
bool f[N];
int n, m, q, d[N], ans[N];
vector < int > s[N], v[N], Q[N];
vector < pair < int , int > > rec[N];
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> m >> q;
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
v[b].pb(a);
}
int sq = sqrt(n);
for (int i = 1; i <= q; ++i) {
int st, k;
cin >> st >> k;
for (int j = 1; j <= k; ++j) {
int x;
cin >> x;
s[i].pb(x);
}
if (k > sq) {
for (int j = 0; j < s[i].size(); ++j) {
f[s[i][j]] = true;
}
d[st] = 1;
ans[i] = -1;
for (int j = st; j >= 1; --j) {
if (d[j]) {
if (!f[j]) {
ans[i] = max(ans[i], d[j] - 1);
}
for (int j2 = 0; j2 < v[j].size(); ++j2) {
int to = v[j][j2];
d[to] = max(d[j] + 1, d[to]);
}
}
}
for (int j = st; j >= 1; --j) d[j] = 0;
for (int j = 0; j < s[i].size(); ++j) {
f[s[i][j]] = false;
}
}
else {
Q[st].pb(i);
}
}
for (int i = 1; i <= n; ++i) {
rec[i].pb({0, i});
for (int j = 0; j < v[i].size(); ++j) {
int to = v[i][j];
for (int k = 0; k < rec[to].size(); ++k) {
++rec[to][k].f;
}
vector < pair < int , int > > ret;
int isz = rec[i].size(), tosz = rec[to].size();
int iid = 0, toid = 0, sz = min(sq + 1, isz + tosz);
while (ret.size() < sz && (toid < tosz || iid < isz)) {
if (toid < tosz && (iid == isz || rec[i][iid] <= rec[to][toid])) {
if (!(ret.size() && ret.back() == rec[to][toid])) {
ret.pb({rec[to][toid].f, rec[to][toid].s});
}
++toid;
}
else
if (iid < isz && (toid == tosz || rec[to][toid] <= rec[i][iid])) {
if (!(ret.size() && ret.back() == rec[i][iid])) {
ret.pb({rec[i][iid].f, rec[i][iid].s});
}
++iid;
}
}
for (int k = 0; k < rec[to].size(); ++k) {
--rec[to][k].f;
}
rec[i] = ret;
}
for (int j = 0; j < Q[i].size(); ++j) {
int id = Q[i][j];
for (int k = 0; k < s[id].size(); ++k) {
int x = s[id][k];
f[x] = true;
}
ans[id] = -1;
for (int k = 0; k < rec[i].size(); ++k) {
int x = rec[i][k].f, idx = rec[i][k].s;
if (!f[idx]) {
ans[id] = max(ans[id], x);
}
}
for (int k = 0; k < s[id].size(); ++k) {
int x = s[id][k];
f[x] = false;
}
}
}
for (int i = 1; i <= q; ++i) {
cout << ans[i] << "\n";
}
}
Compilation message (stderr)
bitaro.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
16 | main () {
| ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int j = 0; j < s[i].size(); ++j) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j2 = 0; j2 < v[j].size(); ++j2) {
| ~~~^~~~~~~~~~~~~
bitaro.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int j = 0; j < s[i].size(); ++j) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int j = 0; j < v[i].size(); ++j) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int k = 0; k < rec[to].size(); ++k) {
| ~~^~~~~~~~~~~~~~~~
bitaro.cpp:76:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
76 | while (ret.size() < sz && (toid < tosz || iid < isz)) {
| ~~~~~~~~~~~^~~~
bitaro.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int k = 0; k < rec[to].size(); ++k) {
| ~~^~~~~~~~~~~~~~~~
bitaro.cpp:98:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int j = 0; j < Q[i].size(); ++j) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int k = 0; k < s[id].size(); ++k) {
| ~~^~~~~~~~~~~~~~
bitaro.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for (int k = 0; k < rec[i].size(); ++k) {
| ~~^~~~~~~~~~~~~~~
bitaro.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int k = 0; k < s[id].size(); ++k) {
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |