이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
#define int int64_t //be careful about this
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)
#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))
template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename T>
void __p(T a) {
cout<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
cout<<"{";
__p(a.first);
cout<<",";
__p(a.second);
cout<<"}\n";
}
template<typename T>
void __p(std::vector<T> a) {
cout<<"{";
for(auto it=a.begin(); it<a.end(); it++)
__p(*it),cout<<",}\n"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
__p(a1);
__p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
cout<<name<<" : ";
__p(arg1);
cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
int bracket=0,i=0;
for(;; i++)
if(names[i]==','&&bracket==0)
break;
else if(names[i]=='(')
bracket++;
else if(names[i]==')')
bracket--;
const char *comma=names+i;
cout.write(names,comma-names)<<" : ";
__p(arg1);
cout<<" | ";
__f(comma+1,args...);
}
void setIO(string s = "") {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin.exceptions(cin.failbit);
cout.precision(15); cout << fixed;
#ifdef ONLINE_JUDGE
if(sz(s)){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define __f(...) 0
#endif
}
#undef int
const int MAX_N = 100000, B = 317, inf = 1e9;
pr<int,int> dis[MAX_N][B]; // 0 -> dis, 1 -> index
bool rem[MAX_N];
int dp[MAX_N];
pr<int,int> tmp[B];
vt<pr<int,int>> help;
// merge as if(a.fr != b.fr) a.fr < b.fr else a.sc < b.sc;
void check(pr<int,int> a[B]){
f(i,0,B-1){
assert(a[i].fr >= a[i+1].fr);
if(a[i].fr == a[i+1].fr) assert(a[i].sc >= a[i+1].sc);
}
return;
}
void merge(pr<int,int> a[B], pr<int,int> b[B]){
//check(a);
//check(b);
unordered_map<int,int> mp;
f(i,0,B) tmp[i] = {-inf,-1};
f(i,0,B){
if(a[i].sc != -1){
ckmax(mp[a[i].sc],a[i].fr);
}
if(b[i].sc != -1){
ckmax(mp[b[i].sc],b[i].fr);
}
}
vt<pr<int,int>> brute;
for(auto [u,v] : mp){
brute.pb({v,u});
}
sort(allr(brute));
f(i,0,min(B,sz(brute))){
tmp[i] = brute[i];
}
/*
int x = 0, y = 0, z = 0;
while(z < B){
if(a[x].sc == -1 && b[y].sc == -1) break;
if(a[x].fr == b[y].fr){
if(a[x].sc == b[y].sc){
tmp[z++] = a[x++] = b[y++];
}else{
if(a[x].sc > b[y].sc){
tmp[z++] = a[x++];
}else{
tmp[z++] = b[y++];
}
}
}else{
if(a[x].fr > b[y].fr){
tmp[z++] = a[x++];
}else{
tmp[z++] = b[y++];
}
}
}
check(tmp);*/
return;
}
signed main(){
setIO();
f(i,0,MAX_N) f(j,0,B) dis[i][j] = {-inf,-1};
mem(rem,false);
int N,M,Q;
rd(N,M,Q);
vt<int> g[N];
f(_,0,M){
int u,v; rd(u,v); --u,--v;
g[v].pb(u);
}
f(i,0,N){
help.clear();
help.pb({0,i});
for(auto j : g[i]){
f(k,0,B) if(dis[j][k].sc != -1) help.pb({dis[j][k].fr + 1, dis[j][k].sc});
}
sort(all(help));
set<int> done;
for(int j = 0; j < B && sz(help) > 0; ++j){
if(!done.count(help.back().sc)){
dis[i][j] = help.back();
done.insert(help.back().sc);
}else{
--j;
}
help.pop_back();
}
}
// f(i,0,N){
// __f("i",i);
// f(j,0,10){
// cout << dis[i][j].sc << ' ';
// }
// cout << endl;
// }
//
// exit(0);
f(_,0,Q){
int T,Y; rd(T,Y); --T;
vt<int> C(Y);
for(auto& i : C) cin >> i, --i;
for(auto& i : C) rem[i] = true;
if(Y < B){
bool done = false;
f(i,0,B){
if(dis[T][i].sc != -1 && !rem[dis[T][i].sc]){
cout << dis[T][i].fr << endl;
done = true; break;
}
}
if(!done) cout << -1 << endl;
}else{
f(i,0,N) dp[i] = -inf;
dp[T] = 0;
for(int i = T; i >= 0; --i){
for(auto j : g[i]){
ckmax(dp[j],dp[i]+1);
}
}
int ans = -1;
f(i,0,N){
if(!rem[i]) ckmax(ans,dp[i]);
}
cout << ans << endl;
}
for(auto& i : C) rem[i] = false;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |