Submission #1063117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063117		anton	Portal (BOI24_portal)	C++17	0 / 100	2098 ms	19200 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+=500;
    b+=500;
    return a*1001+b;
}

bool bounded(p pos){
    return pos.real()>=-500 && pos.real()<=500 && pos.imag()>=-500 && pos.imag()<=500;
}
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(1001*1001);

    for(int i = -500; i<=500; i++){
        for(int j = -500; j<=500; 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 = -500; i<=500; i++){
        for(int j = -500; j<=500; 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