Submission #1264769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264769		Nika533	Portal (BOI24_portal)	C++20	0 / 100	23 ms	9032 KiB

Main

#include <bits/stdc++.h>
// #define int long long
#define pb push_back
using namespace std;

const int N=1e5+5,A=4e5+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;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i];
    // sort(x+1,x+1+n); sort(y+1,y+1+n);
    int num=400;
    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++) {
                for (int jj=1; jj<=n; jj++) {
                    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:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~

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