| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 377581 | cheissmart | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e5 + 7;
vi G[N]; // from
V<pi> who[N];
int n, m, q, k;
bitset<N> s, no;
signed main()
{
IO_OP;
cin >> n >> m >> q;
k = 320;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[v].PB(u);
}
for(int u = 1; u <= n; u++) {
who[u].EB(0, u);
for(int& v:G[u]) {
V<pi>& tt = who[v];
V<pi> ttt;
swap(ttt, who[u]);
who[u].resize(k);
int top = 0;
for(int i = 0, j = 0; i < int(tt.size()) || j < int(ttt.size());) {
auto add = [&] (pi p) {
if(s[p.S] == 0) {
s[p.S] = 1;
who[u][top++] = p;
}
};
if(j == int(ttt.size()) || (i < int(tt.size()) && tt[i].F - 1 < ttt[j].F)) {
add(MP(tt[i].F - 1, tt[i].S));
i++;
} else {
add(ttt[j++]);
}
if(top == k) break;
}
who[u].resize(top);
for(pi& p:who[u]) s[p.S] = 0;
}
}
while(q--) {
int u, y;
cin >> u >> y;
vi x(y);
for(int i = 0; i < y; i++) {
cin >> x[i];
no[x[i]] = 1;
}
if(y >= k) {
vi vis(n + 1), dp(n + 1);
function<int(int)> DP = [&] (int u) {
if(vis[u]) return dp[u];
vis[u] = 1;
if(no[u]) dp[u] = -INF;
else dp[u] = 0;
for(int v:G[u]) {
dp[u] = max(dp[u], DP(v) + 1);
}
return dp[u];
};
cout << max(DP(u), -1) << '\n';
} else {
int ans = -1;
for(pi p:who[u]) {
if(no[p.S] == 0) {
ans = -p.F;
break;
}
}
cout << ans << '\n';
}
for(int i = 0; i < y; i++) no[x[i]] = 0;
}
}