Submission #947333

#TimeUsernameProblemLanguageResultExecution timeMemory
947333MilosMilutinovicIOI Fever (JOI21_fever)C++14
6 / 100
1 ms600 KiB
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} ll readint(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int dx[]={1,0,-1,0}; const int dy[]={0,1,0,-1}; int n; int x[100005],y[100005],dir[100005]; bool was[100005],seen[100005]; int main(){ n=readint(); for(int i=1;i<=n;i++) x[i]=readint(),y[i]=readint(),x[i]*=2,y[i]*=2; int ans=0; for(int d=0;d<4;d++){ for(int i=1;i<=n;i++) was[i]=seen[i]=false; dir[1]=d; was[1]=true; set<pii> st; st.emplace(0,1); while(!st.empty()){ auto it=st.begin(); int t=it->first; int i=it->second; st.erase(it); if(seen[i]) continue; seen[i]=true; for(int j=1;j<=n;j++){ if(was[j]) continue; for(int dd=0;dd<4;dd++){ if(dd==dir[i]) continue; int cx=dx[dir[i]]-dx[dd]; int cy=dy[dir[i]]-dy[dd]; if((x[j]-x[i])*cy!=(y[j]-y[i])*cx) continue; if(cx!=0&&(x[j]-x[i])%cx!=0) continue; if(cy!=0&&(y[j]-y[i])%cy!=0) continue; int ct=(cx==0?(y[j]-y[i])/cy:(x[j]-x[i])/cx); if(ct<t) continue; dir[j]=dd; was[j]=true; st.emplace(ct,j); break; } } } int cnt=0; for(int i=1;i<=n;i++) cnt+=was[i]; ans=max(ans,cnt); } printf("%d\n",ans); }
#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...