이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
vector < pair < int , int > > ret;
int isz = rec[i].size(), tosz = rec[to].size();
int iid = 0, toid = 0, sz = min(sq + 5, isz + tosz);
while (ret.size() < sz && (toid < tosz || iid < isz)) {
if (toid < tosz && (iid == isz || rec[i][iid].f <= rec[to][toid].f + 1)) {
if (!f[rec[to][toid].s]) {
ret.pb({rec[to][toid].f + 1, rec[to][toid].s});
f[rec[to][toid].s] = true;
}
++toid;
}
else
if (iid < isz && (toid == tosz || rec[to][toid].f + 1 <= rec[i][iid].f)) {
if (!f[rec[i][iid].s]) {
f[rec[i][iid].s] = true;
ret.pb(rec[i][iid]);
}
++iid;
}
}
for (int k = 0; k < ret.size(); ++k) {
f[ret[k].s] = false;
}
rec[i] = ret;
ret.clear();
}
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";
}
}
컴파일 시 표준 에러 (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:72: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]
72 | while (ret.size() < sz && (toid < tosz || iid < isz)) {
| ~~~~~~~~~~~^~~~
bitaro.cpp:90: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]
90 | for (int k = 0; k < ret.size(); ++k) {
| ~~^~~~~~~~~~~~
bitaro.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int j = 0; j < Q[i].size(); ++j) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int k = 0; k < s[id].size(); ++k) {
| ~~^~~~~~~~~~~~~~
bitaro.cpp:105: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]
105 | for (int k = 0; k < rec[i].size(); ++k) {
| ~~^~~~~~~~~~~~~~~
bitaro.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | 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... |