제출 #979362

#제출 시각아이디문제언어결과실행 시간메모리
979362lftroqBitaro’s Party (JOI18_bitaro)C++14
0 / 100
2 ms8280 KiB
/* :-=- :%@@@@@@@@@= .#@@@@@%@%@@@@@@= -@@@@@@@@@@@@@@@@@# .+@@@@@@@@@@@@@@@@@@@@. #@@@@@@@@@@@@@@@@@@@@@% .*@@@@@@@@@@@@@@@@@@@@@@@= / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄\ .@@@@@@@@@@@@@@@@@@@@@@@@# | lftroq ♥ | +@@@@@@@@@@@%%@@@@@@@@@@@@- \_________/ .%@@@@@@@@@@%##%@@@@@@@@@@@# // -@@@@@@@@%%%%%%%%%@@@@@@@@@@: -+- =@@@@@%##%#%##**+#@@@@@@@@@@- .+++.%@@@%##%%%%%%%#**+##%%@@@@@@+ +=*%@@@#*###%%#=--+=+*##%@@@@@@%. :*+%@@*+**##*=======+***#@@@@@@@: =+++**%@###*=++=-==++**#@@@@@@@: .**===*%@@@##+=**#*==***@@@@@@@@@: :+++=+*+%%@@%#==+*%#*+=++@@@@@@@@% .**#*+*+**+%#+=---=***+==*@@@@@@@: :**#*+=+**@%##*%#++++--=++#@@@@@@@+-::. =%**###**#@@%*=*%%%%%*==++++%@@@@@@#=-----. .%@@%***###@@@%*++%%%#*===+=++++%@@@@%*=-----=. =**##+=+##@@@@=+%+=***#%@#+**++++%@@%+=-------=: .++===++====@@@@+--==-=#%%%%+++*++++#%+=------==+=. -++--=++-:::::=#@#----+--*%%*+**+++++++==-----===--+= :*+=--++-::::::--=-----==-=%==+%%***++=---=---===-=++: :*+--+=-::::::::---:----+=-=++##***===-::::-+----=*+: .=--:::.:::-=-::---::--------++--=====-::::--:-==++ :=::::::--::::::--=+-:--++++==++--==:::-:::----==+= *-:::::::.....:-++++++++++++++=+=---::::===-:------ :+:--:......:-+++++++++++++++++====---:--=-=----:-:=. :==--:::.:=+++++++++++++++++++++-::===-:-===-----=--: .+=--:::-:=+++++==++++++++++++++=--:.:-===+-------+=-. .+==-----::-+++-:+++=====+++++++=--=======--:----==+=. :+===-----------:-++====+++++++++=--==--+-:------==-:: +=====-::----+-::-+====+++++++++++=---==:-===:-==-==. :+===========+-::::-----+++++++++++*=--======-=+=-=. .=========++=-::::::----:::-++++++*+=+======+++==. .=========-::::::-----:::=+++++**+=+**====-:. . *======-::::::::-:-----++++++++==++++++- #======-:::::::::-------++++++++====+++= =======-:::::::::----:::=+++++++=====+++ =====---:::::::::::------=++++++===+==++= :===-:--:::::::::::-------+++++++===++=++ .===-:--:::::::::::::-----=+++++====++===. .+=-::--::::::::::::-:-----++++++====++=+: .=-:::--::::::::::::-------=+++++===-----+= .=-:::--:::::::::::---------=++++==-----==+=. .=-:::---:::::::::::---------+++===-----===++. .=::::---:::::::-:-----------=++==-:-----===+- .--:::---:::::::--------------=+=----==--===+- .=::::---::::::::::-------===--==-------=--==: .=--::--::::----:---:::::-:----:::-----======- .=---:--:::---::::::--------------------==++++ */ #include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MOD 1000000007ll #define MOD2 998244353ll #define endl '\n' #define PI acos(-1) #define INFINITE 1000000000 #define INFINITE2 1000000000000000000ll #define llll pair<ll,ll> #define ldld pair<ld,ld> #define fi first #define se second #define sqrt sqrtl typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; const int mn=100005; const int block=350; vector<int> graph[mn],rraph[mn]; vector<pair<int,int>> god[mn]; int vis[mn],dp[mn],vv[mn]; void solve() { int n,m,q; cin >> n >> m >> q; while(m--) { int u,v; cin >> u >> v; graph[u].push_back(v); rraph[v].push_back(u); } for(int u=1;u<=n;u++) { for(int j=0;j<(int)rraph[u].size();j++) { int v=rraph[u][j]; vector<pair<int,int>> par; god[v].push_back({0,v}); int a=0,b=0; int sa=god[v].size(),sb=god[u].size(); while(par.size()<block&&(a<sa||b<sb)) { if(b==sb||(a!=sa&&god[v][a].fi+1>=god[u][b].fi+1)) { god[v][a].fi++; par.push_back(god[v][a]); vis[god[v][a].se]=1; god[v][a].fi--; a++; } else { par.push_back(god[u][b]); vis[god[u][b].se]=1; b++; } while(a<sa&&vis[god[v][a].se]) a++; while(b<sb&&vis[god[u][b].se]) b++; } god[v].pop_back(); for(int i=0;i<(int)par.size();i++) vis[par[i].se]=0; swap(god[u],par); } } while(q--) { int t,y; cin >> t >> y; vector<int> c(y); for(int i=0;i<y;i++) { cin >> c[i]; vv[c[i]]=1; } int ans=-1; if(y>=block) { for(int i=1;i<=n;i++) dp[i]=-1; for(int i=t-1;i;i--) { for(int j=0;j<(int)graph[i].size();j++) if(dp[graph[i][j]]!=-1) dp[i]=max(dp[i],dp[graph[i][j]]+1); if(!vv[i]) ans=max(ans,dp[i]); } } else { for(int i=0;i<(int)god[t].size();i++) if(!vv[god[t][i].se]) { ans=god[t][i].fi; break; } } cout << ans << endl; for(int i=0;i<y;i++) vv[c[i]]=0; } } int main() { fastIO //freopen("hanhhhh.inp","r",stdin); //freopen("hanhhhh.out","w",stdout); int t=1; //cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...