oj.uz

Submission #1053095

# Submission time Handle Problem Language Result Execution time Memory
1053095 2024-08-11T08:43:12 Z Faisal_Saqib Portal (BOI24_portal) C++17
1 / 100
 2000 ms 221940 KB 
#warning Check FastIO
#ifdef ONLINE_JUDGE
    #pragma GCC optimize("Ofast")
    #pragma GCC target("avx,avx2,fma")
#endif
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <random>
#include <chrono>
#include <iomanip>
#include <vector>
#include <fstream>
using namespace std;
#define vll vector<ll>
#define sll set<ll>
#define vstr vector<string>
#define ll long long
#define ld long double
#define supra main
#define pb push_back
#define add insert
#define rall(x) rbegin(x),rend(x)
#define all(x) (x).begin(),(x).end()
#define I ios_base::sync_with_stdio(false);
#define Hear cin.tie(NULL);
#define Shots cout.tie(NULL);
#define Ratatatata
#define bits_on(a) (__builtin_popcountll(a))
#define mx_pw2(a) (__builtin_ctzll(a))
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUFFLE(v) shuffle(all(v), RNG); 
const ll inf=LLONG_MAX;
void input(vll& a)
{
    for(auto& i:a)
        cin>>i;
}
void pyn(bool a)
{
    cout<<(a?"YES":"NO")<<endl;
}
ll powmod(ll a,ll b,ll modulo)
{
  if(b==0){
    return 1;
  }
  ll temp=powmod(a,b/2,modulo);
  if(b%2==0){
    return (temp*temp)%modulo;
  }
  else{
    return (a*((temp*temp)%modulo))%modulo;
  }
}

bool Prime(ll n){
    for (ll i = 2; i*i <= n; i++)
        if (n % i == 0)
            return false;
    return (n>1);
}
const int N=3e5;
const int MX=401;
int par[N];
map<pair<int,int>,int>tp;
int nxp=1;
int mapping(int x,int y)
{
    auto it=tp.find({x,y});
    if(it==tp.end())
    {
        tp[{x,y}]=nxp;
        par[nxp]=nxp;
        nxp++;
    }
    return tp[{x,y}];
}
int comp=0;
int get(int x)
{
    if(par[x]==x)return x;
    return par[x]=get(par[x]);
}
void merge(int x,int y)
{
    x=get(x);
    y=get(y);
    if(x==y)return;
    comp--;
    par[x]=y;
}
const int CP=100;
void solve()
{
    ll n;
    cin>>n;  
    for(int j=0;j<N;j++)
    {
        par[j]=j;
    }
    vector<pair<ll,ll>> a;
    for(int i=0;i<n;i++)
        {
            ll x,y;
            cin>>x>>y;
            a.pb({x,y});
        }
    map<pair<ll,ll>,ll> lasp;
    ll tot=0;
    for(int x=-100;x<=100;x++)
    {
        for(int y=-100;y<=100;y++)
        {
            tot++;
            for(int j=0;j<n;j++)
            {
                ll distx=a[j].first-x;
                ll disty=a[j].second-y;
                auto it=lasp.find({distx,disty});
                if(it!=lasp.end())
                    merge((*it).second,mapping(x,y));
                lasp[{distx,disty}]=mapping(x,y);
            }
        }
    }
    if(comp==0)
    {
        cout<<-1<<endl;
    }
    else
    {
        cout<<comp+tot<<endl;
    }
}
int supra(){
    I Hear Shots Ratatatata
    ll tqwertyuiop=1;
    for(int tp=1;tp<=tqwertyuiop;tp++)
    {
        // cout<<"Case #"<<tp<<": ";
        solve();
    }
    return 0;
}
/*
Bro use only in a emergency 
this is kind of hacking
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
*/

Compilation message

Main.cpp:1:2: warning: #warning Check FastIO [-Wcpp]
    1 | #warning Check FastIO
      |  ^~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6540 KB Output is correct
2 Correct 35 ms 9172 KB Output is correct
3 Correct 35 ms 9052 KB Output is correct
4 Correct 40 ms 9032 KB Output is correct
5 Correct 35 ms 9032 KB Output is correct
6 Correct 35 ms 8956 KB Output is correct
7 Correct 41 ms 9152 KB Output is correct
8 Correct 37 ms 9024 KB Output is correct
9 Correct 40 ms 9092 KB Output is correct
10 Correct 37 ms 9128 KB Output is correct
11 Correct 34 ms 9052 KB Output is correct
12 Correct 38 ms 9044 KB Output is correct
13 Correct 22 ms 6484 KB Output is correct
14 Correct 34 ms 9004 KB Output is correct
15 Correct 37 ms 9016 KB Output is correct
16 Correct 37 ms 9180 KB Output is correct
17 Correct 37 ms 9128 KB Output is correct
18 Correct 36 ms 9048 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6540 KB Output is correct
2 Correct 35 ms 9172 KB Output is correct
3 Correct 35 ms 9052 KB Output is correct
4 Correct 40 ms 9032 KB Output is correct
5 Correct 35 ms 9032 KB Output is correct
6 Correct 35 ms 8956 KB Output is correct
7 Correct 41 ms 9152 KB Output is correct
8 Correct 37 ms 9024 KB Output is correct
9 Correct 40 ms 9092 KB Output is correct
10 Correct 37 ms 9128 KB Output is correct
11 Correct 34 ms 9052 KB Output is correct
12 Correct 38 ms 9044 KB Output is correct
13 Correct 22 ms 6484 KB Output is correct
14 Correct 34 ms 9004 KB Output is correct
15 Correct 37 ms 9016 KB Output is correct
16 Correct 37 ms 9180 KB Output is correct
17 Correct 37 ms 9128 KB Output is correct
18 Correct 36 ms 9048 KB Output is correct
19 Correct 48 ms 6588 KB Output is correct
20 Incorrect 60 ms 11580 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6684 KB Output is correct
2 Execution timed out 2081 ms 221940 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6484 KB Output is correct
2 Correct 46 ms 6640 KB Output is correct
3 Correct 20 ms 6488 KB Output is correct
4 Correct 991 ms 8528 KB Output is correct
5 Correct 981 ms 9924 KB Output is correct
6 Correct 1046 ms 10576 KB Output is correct
7 Correct 982 ms 8608 KB Output is correct
8 Correct 936 ms 9112 KB Output is correct
9 Incorrect 79 ms 8592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6540 KB Output is correct
2 Correct 35 ms 9172 KB Output is correct
3 Correct 35 ms 9052 KB Output is correct
4 Correct 40 ms 9032 KB Output is correct
5 Correct 35 ms 9032 KB Output is correct
6 Correct 35 ms 8956 KB Output is correct
7 Correct 41 ms 9152 KB Output is correct
8 Correct 37 ms 9024 KB Output is correct
9 Correct 40 ms 9092 KB Output is correct
10 Correct 37 ms 9128 KB Output is correct
11 Correct 34 ms 9052 KB Output is correct
12 Correct 38 ms 9044 KB Output is correct
13 Correct 22 ms 6484 KB Output is correct
14 Correct 34 ms 9004 KB Output is correct
15 Correct 37 ms 9016 KB Output is correct
16 Correct 37 ms 9180 KB Output is correct
17 Correct 37 ms 9128 KB Output is correct
18 Correct 36 ms 9048 KB Output is correct
19 Correct 48 ms 6588 KB Output is correct
20 Incorrect 60 ms 11580 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6540 KB Output is correct
2 Correct 35 ms 9172 KB Output is correct
3 Correct 35 ms 9052 KB Output is correct
4 Correct 40 ms 9032 KB Output is correct
5 Correct 35 ms 9032 KB Output is correct
6 Correct 35 ms 8956 KB Output is correct
7 Correct 41 ms 9152 KB Output is correct
8 Correct 37 ms 9024 KB Output is correct
9 Correct 40 ms 9092 KB Output is correct
10 Correct 37 ms 9128 KB Output is correct
11 Correct 34 ms 9052 KB Output is correct
12 Correct 38 ms 9044 KB Output is correct
13 Correct 22 ms 6484 KB Output is correct
14 Correct 34 ms 9004 KB Output is correct
15 Correct 37 ms 9016 KB Output is correct
16 Correct 37 ms 9180 KB Output is correct
17 Correct 37 ms 9128 KB Output is correct
18 Correct 36 ms 9048 KB Output is correct
19 Correct 48 ms 6588 KB Output is correct
20 Incorrect 60 ms 11580 KB Output isn't correct
21 Halted 0 ms 0 KB -