이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 dp[N], out[N];
set<pair<int, int>, greater<pair<int, int>>> s[N];
set<int, greater<int>> rev[N];
vector<int> adj[N];
vector<Query> que;
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));
adj[min(a, b)].push_back(max(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(dp, q.town+5, 0);
for (auto it : q.busy) dp[it] = -1;
for (int i=1; i<=q.town; i++) {
if (dp[i] == -1) continue;
for (auto to : adj[i]) dp[to] = max(dp[to], dp[i] + 1);
}
out[q.idx] = dp[q.town];
}
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<=n; i++) {
printf("set %d : ", i);
for (auto it : s[i]) printf("(%d %d) ", it.first, it.second);
printf("\n");
}
*/
for (int i=1; i<=Q; i++) printf("%d\n", out[i]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'int main()':
bitaro.cpp:46:39: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int>, std::greater<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | if (s[now].size() < sq) s[now].insert({val+1, from});
| ~~~~~~~~~~~~~~^~~~
bitaro.cpp:54:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
54 | if (q.busy.size() >= sq) {
| ~~~~~~~~~~~~~~^~~~~
bitaro.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf(" %d %d %d", &n, &m, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf(" %d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf(" %d %d", &in.town, &n_busy);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf(" %d", &a);
| ~~~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |