| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 736583 | browntoad | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
const ll maxn = 2e5+5;
const ll inf = (1ll<<60);
const int iinf = 2147483647;
int n, m, qq;
struct quer{
int nd;
vector<int> ban;
int id;
};
vector<int> ans(maxn), topo(maxn), ind(maxn);
vector<int> tp;
vector<int> graph[maxn];
vector<pii> kth[maxn];
const int bloc = 85;
vector<quer> q1, q2;
void init(){
queue<int> qu;
int cnt = 1;
REP1(i, n){
if (ind[i] == 0){
qu.push(i);
}
}
while(qu.size()){
int x = qu.front(); qu.pop();
topo[x] = cnt;
tp.pb(x);
cnt++;
REP(i, SZ(graph[x])){
ind[graph[x][i]]--;
if (ind[graph[x][i]] == 0){
qu.push(graph[x][i]);
}
}
}
}
void proc1(){
REP1(i, n) kth[i].pb({0, i});
REP(i, SZ(tp)){
int x = tp[i];
sort(ALL(kth[x]));
reverse(ALL(kth[x]));
REP(j, SZ(graph[x])){
REP(l, min(SZ(kth[x]), bloc)){
kth[graph[x][j]].pb({kth[x][l].f+1, kth[x][l].s});
}
}
}
vector<bool> no(n+1);
REP(i, SZ(q1)){
REP(j, SZ(q1[i].ban)){
no[q1[i].ban[j]] = true;
}
int res = iinf;
REP(j, SZ(kth[q1[i].nd])){
if (no[kth[q1[i].nd][j].s]) continue;
res = kth[q1[i].nd][j].f;
break;
}
if (res == iinf) res = -1;
ans[q1[i].id] = res;
REP(j, SZ(q1[i].ban)){
no[q1[i].ban[j]] = false;
}
}
}
void proc2(){
vector<int> dis(n+1);
vector<bool> no(n+1);
REP(i, SZ(q2)){
REP(j, SZ(q2[i].ban)){
no[q2[i].ban[j]] = true;
}
REP(j, topo[q2[i].nd]){
dis[tp[j]] = -iinf;
}
REP(j, topo[q2[i].nd]){
int x = tp[j];
if (!no[x]){
dis[x] = max(dis[x], 0ll);
}
REP(k, SZ(graph[x])){
if (topo[graph[x][k]] > topo[q2[i].nd]) break; // pruning
dis[graph[x][k]] = max(dis[x]+1, dis[graph[x][k]]);
}
}
if (dis[q2[i].nd] < 0) dis[q2[i].nd] = -1;
ans[q2[i].id] = dis[q2[i].nd];
REP(j, SZ(q2[i].ban)){
no[q2[i].ban[j]] = false;
}
}
}
bool cmp(int a, int b){
return topo[a]<topo[b];
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m>>qq;
REP(i, m){
int u, v; cin>>u>>v;
graph[u].pb(v);
ind[v]++;
}
init();
REP1(i, n) {
sort(ALL(graph[i]), cmp);
}
REP(i, qq){
int ndd;
cin>>ndd;
int k; cin>>k;
vector<int> bban;
REP(j, k){
int x; cin>>x;
bban.pb(x);
}
sort(ALL(bban));
if (SZ(bban)<=80){
q1.pb({ndd, bban, i});
}
else
q2.pb({ndd, bban, i});
}
proc1();
proc2();
REP(i, qq){
cout<<ans[i]<<endl;
}
}