| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 543022 | __Variatto | Bitaro’s Party (JOI18_bitaro) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, S=30;/////////////
int n, m, q, a, b, y, t;
int c[MAX], ile[MAX], maxi[MAX];
vector<int>g[MAX], top, g2[MAX];
bool zly[MAX];
void topo(){
for(int i=1; i<=n; i++)
if(!ile[i])
top.pb(i);
for(int i=0; i<top.size(); i++){
int v=top[i];
for(auto s:g[v]){
ile[s]--;
if(!ile[s]) top.pb(s);
}
}
}
void duzo(){
for(auto a: top){
if(zly[a]) maxi[a]=-1;
else maxi[a]=0;
for(auto s:g2[a])
if(maxi[s]!=-1)
maxi[a]=max(maxi[s]+1, maxi[a]);
if(a==t) break;
}
cout<<maxi[t]<<"\n";
}
set<pair<int,int>>all[MAX];
void malo(){
for(auto [f,s]: all[t]){
if(!zly[s]){
cout<<-f<<"\n";
return;
}
}
cout<<-1<<"\n";
}
int old[MAX];
vector<int> odw;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>m>>q;
for(int i=1; i<=m; i++){
cin>>a>>b;
g[a].pb(b), g2[b].pb(a);
ile[b]++;
}
topo();
for(auto a:top){
all[a].insert({0, a});
odw.clear();
odw.pb(a), old[a]=0;
for(auto s:g2[a]){
for(auto [f, s]:all[s]){
odw.pb(s);
if(old[s]<(-f)+1{
if(old[s]!=-1)
all[a].erase(all[a].lower_bound({-old[s], s}));
all[a].insert({-(-f+1), s});
old[s]=-f+1;
}
if(all[a].size()>S+3){
auto it=all[a].end();
it--;
all[a].erase(it);
}
}
}
for(auto s:odw) old[s]=-1;
}
while(q--){
cin>>t>>y;
for(int i=1; i<=y; i++){
cin>>c[i];
zly[c[i]]=true;
}
if(y>S) duzo();
else malo();
for(int i=1; i<=y; i++)
zly[c[i]]=false;
}
}