# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1054261 | manhlinh1501 | Bitaro’s Party (JOI18_bitaro) | C++17 | 4 ms | 15964 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using i64 = long long;
const int MAXN = 2e5 + 5;
const int BLOCK_SIZE = 470;
#define ALL(a) (a).begin(), (a).end()
int N, M, Q;
vector<int> adj[MAXN];
vector<int> radj[MAXN];
bool is_deleted[MAXN];
vector<pii> dp[MAXN];
int dist[MAXN];
bool f[MAXN];
vector<pii> merge(vector<pii> &x, vector<pii> &y) {
vector<pii> z;
int px = 0, py = 0;
while((int)z.size() <= BLOCK_SIZE && px + py < (int)x.size() + (int)y.size()) {
while(px < (int)x.size() && f[x[px].second]) {
++px;
}
while(py < (int)y.size() && f[y[py].second]) {
++py;
}
if(px < (int)x.size() && (py == (int)y.size() || x[px].first > y[py].first + 1)) {
f[x[px].second] = 1;
z.push_back(x[px++]);
} else if(py < (int)y.size()) {
f[y[py].second] = 1;
z.push_back({y[py].first + 1, y[py++].second});
}
}
for(auto [D, x] : z) {
f[x] = 0;
}
return z;
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> Q;
for(int i = 1; i <= M; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
radj[v].emplace_back(u);
}
for(int u = 1; u <= N; u++) {
dp[u].emplace_back(0, u);
for(int v : radj[u])
dp[u] = merge(dp[u], dp[v]);
}
while(Q--) {
int u;
cin >> u;
int sz;
cin >> sz;
vector<int> a(sz, 0);
for(int &x : a) cin >> x;
for(int x : a) is_deleted[x] = true;
if(a.size() >= BLOCK_SIZE) {
int ans = -1;
for(int i = 1; i <= N; i++) dist[i] = -1;
dist[1] = 0;
for(int i = 2; i <= N; i++) {
for(int v : radj[i])
dist[i] = max(dist[i], dist[v] + 1);
}
cout << dist[u] << "\n";
} else {
int ans = -1;
for(auto [x, y] : dp[u]) {
if(is_deleted[y] == false) ans = max(ans, x);
}
cout << ans << "\n";
}
for(int x : a) is_deleted[x] = false;
}
return (0 ^ 0);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |