| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 736340 | 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;
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;
}
}