| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 988426 | ortsac | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int block = 316;
#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second
vector<vector<pii>> far;
vector<bool> freq;
pii aux[500];
void merge(int from, int to) {
vector<pii> leaving;
for (auto u : far[from]) {
leaving.push_back({u.fr + 1, u.se});
}
for (auto u : leaving) {
freq[u.se] = 0;
}
for (auto u : far[to]) {
freq[u.se] = 0;
}
int p1 = 0, p2 = 0;
int n = leaving.size();
int m = far[to].size();
int s = 0;
while ((s < block) && ((p1 < n) || (p2 < m))) {
if (p1 == n) {
// check p2
if (freq[far[to][p2].se]) {
p2++;
continue;
}
aux[s] = far[to][p2];
freq[far[to][p2].se] = 1;
p2++;
} else if (p2 == m) {
// check p1
if (freq[leaving[p1].se]) {
p1++;
continue;
}
aux[s] = leaving[p1];
freq[leaving[p1].se] = 1;
p1++;
} else {
if (freq[leaving[p1].se]) {
p1++;
continue;
}
if (freq[far[to][p2].se]) {
p2++;
continue;
}
if (leaving[p1] > far[to][p2]) {
aux[s] = leaving[p1];
freq[leaving[p1].se] = 1;
p1++;
} else {
aux[s] = far[to][p2];
freq[far[to][p2].se] = 1;
p2++;
}
}
s++;
}
far[to].resize(s);
for (int i = 0; i < s; i++) {
far[to][i] = aux[i];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> adj(n + 1);
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
}
far.resize(n + 1);
freq.resize(n + 1);
for (int i = 1; i <= n; i++) {
far[i].push_back({0, i});
}
for (int i = 1; i <= n; i++) {
for (auto u : adj[i]) {
merge(i, u);
}
}
while (q--) {
int t, y;
cin >> t >> y;
if (y >= block) {
vector<int> mx(t + 1);
while (y--) {
int a;
cin >> a;
mx[a] = -1;
}
for (int i = 1; i <= t; i++) {
if (mx[i] == -1) continue;
for (auto u : adj[i]) {
mx[u] = max(mx[u], mx[i] + 1);
}
}
cout << mx[t] << "\n";
} else {
unordered_map<int, bool> map;
while (y--) {
int a;
cin >> a;
map[a] = 1;
}
bool good = 0;
for (auto u : far[t]) {
if (!map[u.se]) {
cout << u.fr << "\n";
good = 1;
break;
}
}
if (!good) {
cout << "-1\n";
}
}
}
}