oj.uz

Submission #955322

# Submission time Handle Problem Language Result Execution time Memory
955322 2024-03-30T06:21:29 Z vjudge1 IOI Fever (JOI21_fever) C++17
0 / 100
 26 ms 56148 KB 
#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

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")
      |

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56148 KB Output is correct
2 Correct 14 ms 55900 KB Output is correct
3 Correct 13 ms 55900 KB Output is correct
4 Correct 14 ms 55900 KB Output is correct
5 Correct 15 ms 56032 KB Output is correct
6 Correct 13 ms 55900 KB Output is correct
7 Correct 13 ms 55900 KB Output is correct
8 Correct 14 ms 55896 KB Output is correct
9 Correct 13 ms 56032 KB Output is correct
10 Correct 13 ms 55900 KB Output is correct
11 Correct 14 ms 56036 KB Output is correct
12 Correct 14 ms 56016 KB Output is correct
13 Correct 13 ms 55780 KB Output is correct
14 Correct 13 ms 55900 KB Output is correct
15 Correct 13 ms 55900 KB Output is correct
16 Incorrect 15 ms 55900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56148 KB Output is correct
2 Correct 14 ms 55900 KB Output is correct
3 Correct 13 ms 55900 KB Output is correct
4 Correct 14 ms 55900 KB Output is correct
5 Correct 15 ms 56032 KB Output is correct
6 Correct 13 ms 55900 KB Output is correct
7 Correct 13 ms 55900 KB Output is correct
8 Correct 14 ms 55896 KB Output is correct
9 Correct 13 ms 56032 KB Output is correct
10 Correct 13 ms 55900 KB Output is correct
11 Correct 14 ms 56036 KB Output is correct
12 Correct 14 ms 56016 KB Output is correct
13 Correct 13 ms 55780 KB Output is correct
14 Correct 13 ms 55900 KB Output is correct
15 Correct 13 ms 55900 KB Output is correct
16 Incorrect 15 ms 55900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 55896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56148 KB Output is correct
2 Correct 14 ms 55900 KB Output is correct
3 Correct 13 ms 55900 KB Output is correct
4 Correct 14 ms 55900 KB Output is correct
5 Correct 15 ms 56032 KB Output is correct
6 Correct 13 ms 55900 KB Output is correct
7 Correct 13 ms 55900 KB Output is correct
8 Correct 14 ms 55896 KB Output is correct
9 Correct 13 ms 56032 KB Output is correct
10 Correct 13 ms 55900 KB Output is correct
11 Correct 14 ms 56036 KB Output is correct
12 Correct 14 ms 56016 KB Output is correct
13 Correct 13 ms 55780 KB Output is correct
14 Correct 13 ms 55900 KB Output is correct
15 Correct 13 ms 55900 KB Output is correct
16 Incorrect 15 ms 55900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56148 KB Output is correct
2 Correct 14 ms 55900 KB Output is correct
3 Correct 13 ms 55900 KB Output is correct
4 Correct 14 ms 55900 KB Output is correct
5 Correct 15 ms 56032 KB Output is correct
6 Correct 13 ms 55900 KB Output is correct
7 Correct 13 ms 55900 KB Output is correct
8 Correct 14 ms 55896 KB Output is correct
9 Correct 13 ms 56032 KB Output is correct
10 Correct 13 ms 55900 KB Output is correct
11 Correct 14 ms 56036 KB Output is correct
12 Correct 14 ms 56016 KB Output is correct
13 Correct 13 ms 55780 KB Output is correct
14 Correct 13 ms 55900 KB Output is correct
15 Correct 13 ms 55900 KB Output is correct
16 Incorrect 15 ms 55900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56148 KB Output is correct
2 Correct 14 ms 55900 KB Output is correct
3 Correct 13 ms 55900 KB Output is correct
4 Correct 14 ms 55900 KB Output is correct
5 Correct 15 ms 56032 KB Output is correct
6 Correct 13 ms 55900 KB Output is correct
7 Correct 13 ms 55900 KB Output is correct
8 Correct 14 ms 55896 KB Output is correct
9 Correct 13 ms 56032 KB Output is correct
10 Correct 13 ms 55900 KB Output is correct
11 Correct 14 ms 56036 KB Output is correct
12 Correct 14 ms 56016 KB Output is correct
13 Correct 13 ms 55780 KB Output is correct
14 Correct 13 ms 55900 KB Output is correct
15 Correct 13 ms 55900 KB Output is correct
16 Incorrect 15 ms 55900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56148 KB Output is correct
2 Correct 14 ms 55900 KB Output is correct
3 Correct 13 ms 55900 KB Output is correct
4 Correct 14 ms 55900 KB Output is correct
5 Correct 15 ms 56032 KB Output is correct
6 Correct 13 ms 55900 KB Output is correct
7 Correct 13 ms 55900 KB Output is correct
8 Correct 14 ms 55896 KB Output is correct
9 Correct 13 ms 56032 KB Output is correct
10 Correct 13 ms 55900 KB Output is correct
11 Correct 14 ms 56036 KB Output is correct
12 Correct 14 ms 56016 KB Output is correct
13 Correct 13 ms 55780 KB Output is correct
14 Correct 13 ms 55900 KB Output is correct
15 Correct 13 ms 55900 KB Output is correct
16 Incorrect 15 ms 55900 KB Output isn't correct
17 Halted 0 ms 0 KB -