| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 400358 | nikatamliani | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
void maxi(int &x, int y) {
if(x < y) x = y;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
const int C = 1005
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> g(n+1);
vector<vector<int>> r(n+1);
for(int i = 1; i <= m; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v);
r[v].push_back(u);
}
vector<int> dst(n+1);
vector<vector<pair<int, int>>> list(n+1);
for(int i = 1; i <= n; ++i) {
for(int x : r[i]) {
for(auto p : list[x]) maxi(dst[p.second], p.first);
}
for(int x : r[i]) {
for(auto p : list[x]) {
if(dst[p.second] == p.first) {
list[i].push_back({p.first+1, p.second});
dst[p.second] = -1;
}
}
}
list[i].push_back({0, i});
sort(list[i].rbegin(), list[i].rend());
while((int)list[i].size() > C) list[i].pop_back();
for(int x : r[i]) {
for(auto p : list[x]) dst[p.second] = 0;
}
}
vector<bool> blocked(n+1);
while(q--) {
int t, x; cin >> t >> x;
vector<int> v(x);
for(int i = 0; i < x; ++i) {
cin >> v[i];
blocked[v[i]] = 1;
}
int ans = 0;
if(x < C) {
for(pair<int, int> p : list[t]) {
if(!blocked[p.second]) {
ans = p.first;
break;
}
}
} else {
vector<int> dp(n+1, -1e6);
for(int i = 1; i <= t; ++i) {
if(!blocked[i]) {
dp[i] = 0;
}
for(int x : r[i]) {
maxi(dp[i], dp[x]+1);
}
}
ans = dp[t];
}
cout << ans << '\n';
for(int i : v) blocked[i] = 0;
}
}