Submission #1264781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264781		Nika533	Portal (BOI24_portal)	C++20	1 / 100	2095 ms	40520 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
using namespace std;

const int N=1e5+5,A=1e6+5;
int n,x[N],y[N];

int s[A],p[A];
void make_set(int v) {
    p[v]=v; s[v]=1;
}
int find_set(int v) {
    if (p[v]==v) return v;
    return p[v]=find_set(p[v]);
}
void merge_set(int a, int b) {
    a=find_set(a); b=find_set(b);
    if (a==b) return;
    if (s[a]<s[b]) swap(a,b);
    s[a]+=s[b]; p[b]=a;
}

main() {
    cin>>n;
    vector<pii> v;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i];
    vector<int> xx,yy;
    for (int i=1; i<=n; i++) {
        v.pb({x[i],y[i]});
        xx.pb(x[i]); yy.pb(y[i]);
    }
    sort(all(v)); sort(all(xx)); sort(all(yy));
    bool check=true;
    int X=0,Y=0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            X=__gcd(X,x[i]-x[j]);
            Y=__gcd(Y,y[i]-y[j]);
        }
    }
    if (X!=0 && Y!=0) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                int xxx=(x[i]-x[j])/X;
                int yyy=(y[i]-y[j])/Y;
                if (xxx!=yyy) check=false;
            }
        }
    }
    if (xx[0]==xx[n-1] || yy[0]==yy[n-1]) check=true;
    if (check) {
        cout<<-1<<endl;
        return 0;
    }
    // sort(x+1,x+1+n); sort(y+1,y+1+n);
    int num=800;
    for (int i=0; i<=num; i++) {
        for (int j=0; j<=num; j++) {
            make_set(i+j*(num+1));
        }
    }
    for (int i=0; i<=num; i++) {
        for (int j=0; j<=num; j++) {
            int num1=i+j*(num+1);
            for (int ii=1; ii<=n; ii++) {
                int jj=1;
                int i1=i+x[ii]-x[jj];
                int j1=j+y[ii]-y[jj];
                int num2=i1+j1*(num+1);
                if (0<=i1 && i1<=num && 0<=j1 && j1<=num) {
                    merge_set(num1,num2);
                }
            }
            for (int jj=1; jj<=n; jj++) {
                int ii=1;
                int i1=i+x[ii]-x[jj];
                int j1=j+y[ii]-y[jj];
                int num2=i1+j1*(num+1);
                if (0<=i1 && i1<=num && 0<=j1 && j1<=num) {
                    merge_set(num1,num2);
                }
            }
        }
    }
    set<int> myset;
    for (int i=0; i<=num; i++) {
        for (int j=0; j<=num; j++) {
            myset.insert(find_set(i+j*(num+1)));
        }
    }
    cout<<myset.size()<<endl;
}

Compilation message (stderr)

Main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main() {
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35