Submission #955322

#TimeUsernameProblemLanguageResultExecution timeMemory
955322vjudge1IOI Fever (JOI21_fever)C++17
0 / 100
26 ms56148 KiB
#include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert #define int ll const int MAX=1e5+15; const int B=300; const int N=104; const int block=400; const int maxB=MAX/B+10; const ll inf=1e18; const int mod=998244353; const int mod1=1e9+9; const ld eps=1e-9; int dx[8]={1,0,-1,0,1,-1,-1,1}; int dy[8]={0,1,0,-1,1,-1,1,-1}; int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } int n; pii a[MAX]; set<int> d; map<int,int> mp; vector<int> g[MAX*16]; int cur; int pos(int v,int nap){ return (nap-1)*n+v; } vector<pii> vec[MAX]; int vertin[MAX],vertout[MAX]; void add(int x,int y){ g[x].pb(y); } int cnt; bool was[MAX]; int use[16*MAX]; void dfs(int v){ use[v]=1; if(v<=4*n){ if(!was[v%n])cnt++; was[v%n]=1; // cout<<v%n<<"\n"; } for(auto to:g[v]){ if(use[to])continue; dfs(to); } } void solve(){ cin>>n; cur=4*n; for(int i=1;i<=n;i++){ cin>>a[i].F>>a[i].S; } { for(int i=1;i<=n;i++)d.in(a[i].F+a[i].S); int gg=0; for(int x:d)mp[x]=++gg; for(int i=1;i<=n;i++){ vec[mp[a[i].F+a[i].S]].pb({a[i].F,i}); } for(int i=1;i<=n;i++){ sort(all(vec[i])); for(int j=0;j<sz(vec[i]);j++){ if(j>0){ add(pos(vec[i][j].S,1),vertin[j-1]); add(vertout[j-1],pos(vec[i][j].S,1)); } vertin[j]=++cur; if(j>0)add(vertin[j],vertin[j-1]); add(vertin[j],pos(vec[i][j].S,2)); vertout[j]=++cur; if(j>0)add(vertout[j-1],vertout[j]); add(pos(vec[i][j].S,2),vertout[j]); } for(int j=0;j<sz(vec[i]);j++){ if(j>0){ add(pos(vec[i][j].S,4),vertin[j-1]); add(vertout[j-1],pos(vec[i][j].S,4)); } vertin[j]=++cur; if(j>0)add(vertin[j],vertin[j-1]); add(vertin[j],pos(vec[i][j].S,3)); vertout[j]=++cur; if(j>0)add(vertout[j-1],vertout[j]); add(pos(vec[i][j].S,3),vertout[j]); } } } d.clear(); mp.clear(); for(int i=1;i<=n;i++)vec[i].clear(); { for(int i=1;i<=n;i++)d.in(a[i].F-a[i].S); int gg=0; for(int x:d)mp[x]=++gg; for(int i=1;i<=n;i++){ vec[mp[a[i].F-a[i].S]].pb({a[i].F,i}); } for(int i=1;i<=n;i++){ sort(all(vec[i])); reverse(all(vec[i])); for(int j=0;j<sz(vec[i]);j++){ if(j>0){ add(pos(vec[i][j].S,1),vertin[j-1]); add(vertout[j-1],pos(vec[i][j].S,1)); } vertin[j]=++cur; if(j>0)add(vertin[j],vertin[j-1]); add(vertin[j],pos(vec[i][j].S,4)); vertout[j]=++cur; if(j>0)add(vertout[j-1],vertout[j]); add(pos(vec[i][j].S,4),vertout[j]); } for(int j=0;j<sz(vec[i]);j++){ if(j>0){ add(pos(vec[i][j].S,2),vertin[j-1]); add(vertout[j-1],pos(vec[i][j].S,2)); } vertin[j]=++cur; if(j>0)add(vertin[j],vertin[j-1]); add(vertin[j],pos(vec[i][j].S,3)); vertout[j]=++cur; if(j>0)add(vertout[j-1],vertout[j]); add(pos(vec[i][j].S,3),vertout[j]); } } } int ans=0; for(int i=1;i<=4;i++){ dfs(pos(1,i)); ans=max(ans,cnt); cnt=0; mem(use,0); mem(was,0); } cout<<ans<<"\n"; } signed main(){ // freopen("help.in","r",stdin); // freopen("help.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // prec(); int t=1; // cin>>t; while(t--)solve(); }

Compilation message (stderr)

fever.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
fever.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...