| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 386964 | jeroenodb | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
const int K = 100;
int n;
vi adj[mxN];
pi dp[mxN][K];
int sz[mxN];
pi merger[2*K];
int input[mxN];
bitset<mxN> banned;
int longest[mxN];
pi* mymerge(pi* p1, pi* e1, pi* p2, pi* e2) {
pi* a= merger;
while(p1!=e1 and p2!=e2 and a-merger<k) {
if(banned[p1->second]) p1++;
else if(banned[p2->second]) p2++;
else if(*p1 > *p2) {
banned[p1->second]=true;
*(a++) = *(p1++);
} else {
banned[p2->second]=true;
*(a++) = *(p2++);
}
}
while(p1!=e1) {
*a = *p1;
if(!banned[p1++->second])
a++;
}
while(p2!=e2) {
*a = *p2;
if(!banned[p2++->second])
a++;
}
for(pi* i =merger;i!=a;++i) banned[i->second] = false;
return a;
}
void precomp() {
// find best K for every party position
for(int i=0;i<n;++i) {
dp[i][0] = {-1,i};
sz[i] = 1;
for(int to: adj[i]) {
auto iter = mymerge(dp[i],dp[i]+sz[i], dp[to],dp[to]+sz[to]);
// wrong, because answer may be more than one time in the dp array, more difficult merge is needed
sz[i] = min(K,(int)(iter-merger));
copy(merger,merger + sz[i], dp[i]);
}
for(int j=0;j<sz[i];++j) dp[i][j].first++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m,q; cin >> n >> m >> q;
while(m--) {
int a,b; cin >> a >> b; --a,--b;
adj[b].push_back(a);
}
precomp();
while(q--) {
int party, y; cin >> party >> y; party--;
for(int i=0;i<y;++i) {
cin >> input[i]; input[i]--;
banned[input[i]] =true;
}
if(y<K) {
// Have stored the answer already in DP, just pick it out
int ans = -1;
for(int i=0;i<sz[party];++i) {
auto [length,to] = dp[party][i];
if(!banned[to]) {
ans = length;
break;
}
}
cout << ans << '\n';
} else {
// Do the calculation of longest paths all over. O(M) worstcase, but only happens n/k times
for(int i=0;i<=party;++i) {
if(banned[i])
longest[i] = -oo;
else longest[i] = 0;
for(int to: adj[i]) {
longest[i] = max(longest[i],longest[to]+1);
}
}
cout << (longest[party]<0?-1:longest[party]) << '\n';
}
for(int i=0;i<y;++i) banned[input[i]]=false;
}
}