| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 656024 | nolimiya | 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>
#include <math.h>
//in the name of god,aka allah
//agha moosa mam baladim
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<long long , long long>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 3e5;
const long long mod = 1e9 + 7 ;
typedef long long ll;
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
//cout << mid <<" " << mid*mid-mid <<endl;
if (((mid-1)*mid)/2 < m) return 0;
return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<int> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm],gos[maxm];
ll pedaret[maxm];
ll get_par(ll v){
if (pedaret[v]==v) return v;
return pedaret[v] = get_par(pedaret[v]);
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<pi> st;
ll rp[maxm];
//ll rw[maxm][maxm];
map<ll,ll> mp;
const int sq = 502;
pi w[maxm][sq];
pi dp[sq*2+1];
void merge(int x, int y){
ss=mm=0;
while(mm<sq||ss<sq){
if(ss==sq||(mm<sq&&w[y][mm].first>w[x][ss].first+1)) dp[ss+mm]=w[y][mm] , mm++;
else dp[ss+mm]=w[x][ss] , dp[ss+mm].first++ , ss++;
}
//cout<<66;
mid = 0;
for(int i=0; i<2*sq&&mid<sq; i++){
if(dp[i].second!=-1&&!vis[dp[i].second]) w[y][mid++]=dp[i] , vis[dp[i].second]=1;// , mid+=dp[i];
}
//cout<<67;
for(int i=0; i<2*sq; i++) if(dp[i].second!=-1) vis[dp[i].second]=0;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int q;
cin >>n>>m>>q;
for(int i=0; i<m; i++){
cin >>l>>r,l--,r--;
g[r].push_back(l);
}
for(int i=0; i<n; i++){
for (int j=0; j<sq; j++) w[i][j] = {-1,-1};
w[i][0]=pi{0,i};
for(auto x:g[i]) merge(x,i);
}
//cout<<65;
while(q--){
cin>>l>>r;
l--;
vector<int> vec(r);
for(int i=0; i<r; i++){
cin>>vec[i];
vec[i]--;
gos[vec[i]]=1;
}
vec.shrink_to_fit();
mid=-1;
if(r>=sq){
for(int i=0; i<=l; i++){
if(gos[i]) pedaret[i]=-1;
else pedaret[i]=0;
for(auto x:g[i]){
if(pedaret[x]!=-1) pedaret[i]=max(pedaret[i],pedaret[x]+1);
//cout<<pedaret[i]<<" "<<pedaret[x]<<endl;
}
}
mid=pedaret[l];
}
else{
for(int i=0; i<sq; i++) if(!gos[w[l][i].second]){
mid=max(mid,w[l][i].first);
//cout<<i<<" "<<mid<<endl;
}
}
for(auto x:vec) gos[x]=0;
cout<<mid<<endl;
}
}