Submission #435960

#	Time	Username	Problem	Language	Result	Execution time	Memory
435960		79brue	Fountain Parks (IOI21_parks)	C++17	25 / 100	939 ms	28996 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

typedef long long ll;

struct Point{
    int x, y, idx;
    Point(){}
    Point(int x, int y, int idx): x(x), y(y), idx(idx){}

    bool operator<(const Point &r)const{
        if(x==r.x) return x<r.x;
        return y<r.y;
    }
};

struct Edge{
    int u, v, idx;
    Edge(){}
    Edge(int u, int v, int idx): u(u), v(v), idx(idx){}

    bool operator==(const Edge &r)const{
        return idx==r.idx;
    }
};

struct dat{
    int x, y;
    vector<Edge> vec;
    dat(){}
    dat(int x, int y, vector<Edge> vec): x(x), y(y), vec(vec){}

    bool operator<(const dat &r)const{
        if(vec.size() != r.vec.size()) return vec.size() < r.vec.size();
        return make_pair(x, y) < make_pair(r.x, r.y);
    }
};

int xx[]={1, -1, 0, 0}, yy[]={0, 0, 1, -1};

int n;
Point arr[200002];
map<pair<int, int>, int> idx;

int par[200002];
int edgeU[400002], edgeV[400002], edgeCnt;
int edgeA[400002], edgeB[400002];

int find(int x){
    if(x==par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    par[y] = x;
}

set<pair<int, int> > criticalPoints;
map<pair<int, int>, vector<pair<int, int> > > link;

int findPoint(int x, int y){
    if(idx.find(make_pair(x, y)) == idx.end()) return -1;
    return idx[make_pair(x, y)];
}

bool findCritical(int x, int y){
    return criticalPoints.find(make_pair(x, y)) != criticalPoints.end();
}

set<pair<pair<int, int>, pair<int, int> > > avoid;

map<pair<int, int>, bool> visited;
void dfs(pair<int, int> p){
    int x = p.first, y = p.second;
    visited[p] = 1;
    for(auto nxt: link[p]){
        if(visited[nxt]) continue;
        if(x){
            if(x == nxt.first) avoid.insert(make_pair(make_pair(x, min(y, nxt.second)), make_pair(x, max(y, nxt.second))));
            else               avoid.insert(make_pair(make_pair(min(x, nxt.first), y), make_pair(max(x, nxt.first), y)));
        }
        dfs(nxt);
    }
}

bool firstTime;
int construct_roads(vector<int> x, vector<int> y) {
    n = (int)x.size();
    for(int i=0; i<n; i++){
        arr[i] = Point(x[i], y[i], i);
        par[i] = i;
        idx[make_pair(x[i], y[i])] = i;
    }

    for(int i=0; i<n; i++){
        if(findPoint(arr[i].x+2, arr[i].y) != -1){
            edgeU[edgeCnt] = i, edgeV[edgeCnt] = idx[make_pair(arr[i].x+2, arr[i].y)];
            edgeA[edgeCnt] = arr[i].x+1;
            edgeB[edgeCnt] = (arr[i].x+arr[i].y) % 4 == 0 ? arr[i].y-1 : arr[i].y+1;
            edgeCnt++;
        }
        if(findPoint(arr[i].x, arr[i].y+2) != -1){
            edgeU[edgeCnt] = i, edgeV[edgeCnt] = idx[make_pair(arr[i].x, arr[i].y+2)];
            edgeA[edgeCnt] = (arr[i].x+arr[i].y) % 4 == 0 ? arr[i].x+1 : arr[i].x-1;
            edgeB[edgeCnt] = arr[i].y+1;
            edgeCnt++;
        }
    }

    for(int i=0; i<edgeCnt; i++) merge(edgeU[i], edgeV[i]);
    for(int i=0; i<n; i++) if(find(0) != find(i)) return 0;

    for(int i=0; i<n; i++){
        if(findPoint(arr[i].x, arr[i].y+2) == -1 || findPoint(arr[i].x+2, arr[i].y) == -1 || findPoint(arr[i].x+2, arr[i].y+2) == -1) continue;
        criticalPoints.insert(make_pair(arr[i].x+1, arr[i].y+1));
    }

    pair<int, int> origin (0, 0);
    for(auto p: criticalPoints){
        if((p.first+p.second)%4 == 0){
            if(findCritical(p.first, p.second + 2)) link[p].push_back(make_pair(p.first, p.second+2));
            if(findCritical(p.first, p.second - 2)) link[p].push_back(make_pair(p.first, p.second-2));
            if(!findCritical(p.first-2, p.second)){
                link[origin].push_back(make_pair(p.first-2, p.second));
                link[make_pair(p.first-2, p.second)].push_back(p);
            }
            if(!findCritical(p.first+2, p.second)){
                link[origin].push_back(make_pair(p.first+2, p.second));
                link[make_pair(p.first+2, p.second)].push_back(p);
            }
        }
        else{
            if(findCritical(p.first + 2, p.second)) link[p].push_back(make_pair(p.first+2, p.second));
            if(findCritical(p.first - 2, p.second)) link[p].push_back(make_pair(p.first-2, p.second));
            if(!findCritical(p.first, p.second-2)){
                link[origin].push_back(make_pair(p.first, p.second-2));
                link[make_pair(p.first, p.second-2)].push_back(p);
            }
            if(!findCritical(p.first, p.second+2)){
                link[origin].push_back(make_pair(p.first, p.second+2));
                link[make_pair(p.first, p.second+2)].push_back(p);
            }
        }
    }

    dfs(origin);

    int pnt = 0;
    for(int i=0; i<edgeCnt; i++){
        auto minPoint = make_pair(min(arr[edgeU[i]].x, arr[edgeV[i]].x), min(arr[edgeU[i]].x, arr[edgeV[i]].x));
        auto maxPoint = make_pair(max(arr[edgeU[i]].x, arr[edgeV[i]].x), max(arr[edgeU[i]].x, arr[edgeV[i]].x));
        if(avoid.find(make_pair(minPoint, maxPoint)) != avoid.end()) continue;

        swap(edgeU[i], edgeU[pnt]);
        swap(edgeV[i], edgeV[pnt]);
        swap(edgeA[i], edgeA[pnt]);
        swap(edgeB[i], edgeB[pnt]);
        pnt++;
    }

    build(vector<int>(edgeU, edgeU+n-1), vector<int>(edgeV, edgeV+n-1), vector<int>(edgeA, edgeA+n-1), vector<int>(edgeB, edgeB+n-1));
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30