# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
736340 | browntoad | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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){
topo[i] = cnt;
tp.pb(i);
qu.push(i);
cnt++;
}
}
while(qu.size()){
int x = qu.front(); qu.pop();
REP(i, SZ(graph[x])){
ind[graph[x][i]]--;
if (ind[graph[x][i]] == 0){
topo[graph[x][i]] = cnt;
tp.pb(graph[x][i]);
cnt++;
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});
}
}
}
}
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]++;
}
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});
}
init();
proc1();
proc2();
REP(i, qq){
cout<<ans[i]<<endl;
}
}