이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
const int N = 2e5 + 5, MOD = 1e9 + 7, SQ = 0;//sqrt(N);
vector<int> adj[N], vec[N], Q[N];
int n, m, q, T[N], prv[N];
unordered_set<int> st[N];
int cur, dis[N], ans[N];
vector<pair<int, int> > V[N];
void _merge(int v, int u) {
/*set<pair<int, int> > S;
unordered_set<int> s;
cur++;
for (auto [x, y] : V[v]) {
s.insert(y);
if (prv[y] < cur || dis[y] < x) {
dis[y] = x;
prv[y] = cur;
}
}
for (auto [x, y] : V[u]) {
s.insert(y);
if (prv[y] < cur || dis[y] < x + 1) {
dis[y] = x + 1;
prv[y] = cur;
}
}
V[v].clear();
for (auto x : s) {
S.insert(mp(-dis[x], x));
}
while (!S.empty() && V[v].size() < SQ) {
V[v].pb(mp(-S.begin()->fi, S.begin()->se));
S.erase(S.begin());
}
return;*/
cur++;
vector<pair<int, int> > tmp;
int l = 0, r = 0;
while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
while (l < V[v].size() && prv[V[v][l].se] == cur)
l++;
while (r < V[u].size() && prv[V[u][r].se] == cur)
r++;
if (l == V[v].size() || r == V[u].size())
break;
pair<int, int> pl = V[v][l], pr = V[u][r];
pr.fi++;
if (pl >= pr) {
tmp.pb(pl);
prv[pl.se] = cur;
l++;
}
else {
tmp.pb(pr);
prv[pr.se] = cur;
r++;
}
}
while (tmp.size() < SQ && l < V[v].size()) {
while (l < V[v].size() && prv[V[v][l].se] == cur)
l++;
if (l == V[v].size())
break;
tmp.pb(V[v][l]);
prv[V[v][l].se] = cur;
l++;
}
while (tmp.size() < SQ && r < V[u].size()) {
while (r < V[u].size() && prv[V[u][r].se] == cur) {
r++;
}
if (r == V[u].size())
break;
tmp.pb(V[u][r]);
tmp.back().fi++;
prv[V[u][r].se] = cur;
r++;
}
swap(V[v], tmp);
}
void brute_force(int r) {
for (int j = 1; j <= r; j++)
dis[j] = -1;
dis[r] = 0;
for (int i = r; i > 1; i--) {
for (auto j : adj[i]) {
dis[j] = max(dis[j], dis[i] + 1);
}
}
}
void solve() {
cin >> n >> m >> q;
for (int i = 0; i < m; i++) {
int s, e; cin >> s >> e;
adj[e].pb(s);
}
for (int i = 0; i < q; i++) {
cin >> T[i];
int y; cin >> y;
for (int j = 0; j < y; j++) {
int x; cin >> x;
if (x <= T[i])
st[i].insert(x);
}
Q[T[i]].pb(i);
}
for (int i = 1; i <= n; i++) {
V[i].pb(mp(0, i));
for (auto u : adj[i]) {
_merge(i, u);
}
/*cout << i << " : ";
for (auto x : V[i])
cout << x.fi << ' ' << x.se << endl;*/
bool ok = false;
vector<pair<int, int> > tmp;
for (auto j : Q[i]) {
if (st[j].size() >= SQ) {
tmp.clear();
set<pair<int, int> > S;
//if (!ok) {
brute_force(i);
for (int k = 1; k <= i; k++)
if (dis[k] >= 0) {
S.insert(mp(-dis[k], k));
}
//sort(tmp.begin(), tmp.end(), greater<pair<int, int> >());
ok = true;
//}
int inx = 0;
while (!S.empty() && st[j].find(S.begin()->se) != st[j].end())
S.erase(S.begin());
ans[j] = (S.empty() ? -1 : -S.begin()->fi);
//ans[j] = (inx == tmp.size() ? -1 : tmp[inx].fi);
}
else {
assert(n == 0);
int inx = 0;
while (inx < V[i].size() && st[j].find(V[i][inx].se) != st[j].end())
inx++;
ans[j] = (inx == V[i].size() ? -1 : V[i][inx].fi);
}
}
/*if (ok) {
vector<pair<int, int> > tmp;
brute_force(i);
for (int j = 1; j <= i; j++) {
tmp.pb(mp(dis[j], j));
}
sort(tmp.begin(), tmp.end(), greater<pair<int, int> >());
for (auto j : Q[i]) {
}
}*/
}
for (int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'void _merge(int, int)':
bitaro.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:48:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while (l < V[v].size() && r < V[u].size() && tmp.size() < SQ) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | while (l < V[v].size() && prv[V[v][l].se] == cur)
| ~~^~~~~~~~~~~~~
bitaro.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | while (r < V[u].size() && prv[V[u][r].se] == cur)
| ~~^~~~~~~~~~~~~
bitaro.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (l == V[v].size() || r == V[u].size())
| ~~^~~~~~~~~~~~~~
bitaro.cpp:53:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (l == V[v].size() || r == V[u].size())
| ~~^~~~~~~~~~~~~~
bitaro.cpp:68:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while (tmp.size() < SQ && l < V[v].size()) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:69:18: 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 | while (l < V[v].size() && prv[V[v][l].se] == cur)
| ~~^~~~~~~~~~~~~
bitaro.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | if (l == V[v].size())
| ~~^~~~~~~~~~~~~~
bitaro.cpp:77:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | while (tmp.size() < SQ && r < V[u].size()) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | while (r < V[u].size() && prv[V[u][r].se] == cur) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (r == V[u].size())
| ~~^~~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:141:21: warning: unused variable 'inx' [-Wunused-variable]
141 | int inx = 0;
| ^~~
bitaro.cpp:150:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | while (inx < V[i].size() && st[j].find(V[i][inx].se) != st[j].end())
| ~~~~^~~~~~~~~~~~~
bitaro.cpp:152:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | ans[j] = (inx == V[i].size() ? -1 : V[i][inx].fi);
| ~~~~^~~~~~~~~~~~~~
bitaro.cpp:126:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
126 | bool ok = false;
| ^~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
