Submission #1063115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063115		anton	Portal (BOI24_portal)	C++17	0 / 100	2085 ms	7512 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define int long long 
#define pii pair<int, int>
#define p complex<int>

const int MAX_N = 3e5+1;
int N;
int to_id(int a, int b){
    a+=200;
    b+=200;
    return a*401+b;
}

bool bounded(p pos){
    return pos.real()>=-200 && pos.real()<=200 && pos.imag()>=-200 && pos.imag()<=200;
}
struct DSU{
    vector<int> anc;
    vector<int> sz;

    DSU(int len){
        anc.resize(len);
        sz.resize(len, 1);

        for(int i = 0; i<len; i++){
            anc[i] = i;
        }
    }

    int C(int u){
        if(anc[u] == u){
            return u;
        }
        int v= C(anc[u]);
        anc[u] =v;
        return v;
    }

    void merge(int a, int b){
        a = C(a);
        b= C(b);
        if(a== b){
            return;
        }
        if(sz[a]<sz[b]){
            swap(a, b);
        }


        anc[b] = a;
        sz[a] += sz[b];
    }
};


signed main(){
    cin>>N;

    vector<p> portals;

    for(int i = 0; i<N; i++){
        int a, b;
        cin>>a>>b;
        portals.push_back({a, b});
    }

    vector<p> merges;

    for(int i = 0; i<1; i++){
        for(int j = i+1; j<N; j++){
            merges.push_back(portals[i]-portals[j]);
        }
    }
    if(merges.size() == 0){
        cout<<-1<<endl;
        return 0;
    }
    DSU dsu(401*401);

    for(int i = -200; i<=200; i++){
        for(int j = -200; j<=200; j++){
            p cur_p= {i, j};
            for(auto e: merges){
                p other_p = cur_p +e;
                if(bounded(other_p)){
                    dsu.merge(to_id(cur_p.real(), cur_p.imag()), to_id(other_p.real(),other_p.imag()));
                }
            }
        }
    }


    int res= 0;
    for(int i = -200; i<=200; i++){
        for(int j = -200; j<=200; j++){
            if(dsu.anc[to_id(i, j)] == to_id(i, j)){
                res++;
            }
        }
    }

    cout<<res<<endl;
}

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