Submission #560709

#	Time	Username	Problem	Language	Result	Execution time	Memory
560709		AlperenT	Fountain Parks (IOI21_parks)	C++17	70 / 100	1389 ms	114224 KiB

parks

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

using namespace std;

const int N = 2e5 + 5;

struct DSU{
    int par[N], setsize[N], setcnt;

    void reset(int n){
        for(int i = 0; i < n; i++) par[i] = i, setsize[i] = 1;
        setcnt = n;
    }

    int setfind(int a){
        if(a == par[a]) return a;
        else return par[a] = setfind(par[a]);
    }

    void setunion(int a, int b){
        a = setfind(a), b = setfind(b);

        if(a != b){
            if(setsize[b] > setsize[a]) swap(a, b);
            par[b] = par[a];
            setsize[a] += setsize[b];
            setcnt--;
        }
    }
};

DSU dsu;

struct Point{
    int x, y;

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

map<Point, int> nodes;
map<Point, Point> edges;
map<Point, bool> vis;

bool check(Point p){
    if(nodes.find({p.x - 1, p.y - 1}) != nodes.end() && nodes.find({p.x - 1, p.y + 1}) != nodes.end() && dsu.setfind(nodes[{p.x - 1, p.y - 1}]) != dsu.setfind(nodes[{p.x - 1, p.y + 1}])){
        edges[{nodes[{p.x - 1, p.y - 1}], nodes[{p.x - 1, p.y + 1}]}] = p;
        dsu.setunion(nodes[{p.x - 1, p.y - 1}], nodes[{p.x - 1, p.y + 1}]);
        return true;
    }
    if(nodes.find({p.x - 1, p.y - 1}) != nodes.end() && nodes.find({p.x + 1, p.y - 1}) != nodes.end() && dsu.setfind(nodes[{p.x - 1, p.y - 1}]) != dsu.setfind(nodes[{p.x + 1, p.y - 1}])){
        edges[{nodes[{p.x - 1, p.y - 1}], nodes[{p.x + 1, p.y - 1}]}] = p;
        dsu.setunion(nodes[{p.x - 1, p.y - 1}], nodes[{p.x + 1, p.y - 1}]);
        return true;
    }
    if(nodes.find({p.x + 1, p.y - 1}) != nodes.end() && nodes.find({p.x + 1, p.y + 1}) != nodes.end() && dsu.setfind(nodes[{p.x + 1, p.y - 1}]) != dsu.setfind(nodes[{p.x + 1, p.y + 1}])){
        edges[{nodes[{p.x + 1, p.y - 1}], nodes[{p.x + 1, p.y + 1}]}] = p;
        dsu.setunion(nodes[{p.x + 1, p.y - 1}], nodes[{p.x + 1, p.y + 1}]);
        return true;
    }
    if(nodes.find({p.x + 1, p.y + 1}) != nodes.end() && nodes.find({p.x - 1, p.y + 1}) != nodes.end() && dsu.setfind(nodes[{p.x + 1, p.y + 1}]) != dsu.setfind(nodes[{p.x - 1, p.y + 1}])){
        edges[{nodes[{p.x + 1, p.y + 1}], nodes[{p.x - 1, p.y + 1}]}] = p;
        dsu.setunion(nodes[{p.x + 1, p.y + 1}], nodes[{p.x - 1, p.y + 1}]);
        return true;
    }

    return false;
}

void dfs(Point p){
    if(nodes.find({p.x - 1, p.y - 1}) != nodes.end() && nodes.find({p.x - 1, p.y + 1}) != nodes.end() && !vis[{p.x - 2, p.y}] && dsu.setfind(nodes[{p.x - 1, p.y - 1}]) != dsu.setfind(nodes[{p.x - 1, p.y + 1}])){
        edges[{nodes[{p.x - 1, p.y - 1}], nodes[{p.x - 1, p.y + 1}]}] = {p.x - 2, p.y};
        dsu.setunion(nodes[{p.x - 1, p.y - 1}], nodes[{p.x - 1, p.y + 1}]);
        vis[{p.x - 2, p.y}] = true;
        dfs({p.x - 2, p.y});
    }
    if(nodes.find({p.x - 1, p.y - 1}) != nodes.end() && nodes.find({p.x + 1, p.y - 1}) != nodes.end() && !vis[{p.x, p.y - 2}] && dsu.setfind(nodes[{p.x - 1, p.y - 1}]) != dsu.setfind(nodes[{p.x + 1, p.y - 1}])){
        edges[{nodes[{p.x - 1, p.y - 1}], nodes[{p.x + 1, p.y - 1}]}] = {p.x, p.y - 2};
        dsu.setunion(nodes[{p.x - 1, p.y - 1}], nodes[{p.x + 1, p.y - 1}]);
        vis[{p.x, p.y - 2}] = true;
        dfs({p.x, p.y - 2});
    }
    if(nodes.find({p.x + 1, p.y - 1}) != nodes.end() && nodes.find({p.x + 1, p.y + 1}) != nodes.end() && !vis[{p.x + 2, p.y}] && dsu.setfind(nodes[{p.x + 1, p.y - 1}]) != dsu.setfind(nodes[{p.x + 1, p.y + 1}])){
        edges[{nodes[{p.x + 1, p.y - 1}], nodes[{p.x + 1, p.y + 1}]}] = {p.x + 2, p.y};
        dsu.setunion(nodes[{p.x + 1, p.y - 1}], nodes[{p.x + 1, p.y + 1}]);
        vis[{p.x + 2, p.y}] = true;
        dfs({p.x + 2, p.y});
    }
    if(nodes.find({p.x + 1, p.y + 1}) != nodes.end() && nodes.find({p.x - 1, p.y + 1}) != nodes.end() && !vis[{p.x, p.y + 2}] && dsu.setfind(nodes[{p.x + 1, p.y + 1}]) != dsu.setfind(nodes[{p.x - 1, p.y + 1}])){
        edges[{nodes[{p.x + 1, p.y + 1}], nodes[{p.x - 1, p.y + 1}]}] = {p.x, p.y + 2};
        dsu.setunion(nodes[{p.x + 1, p.y + 1}], nodes[{p.x - 1, p.y + 1}]);
        vis[{p.x, p.y + 2}] = true;
        dfs({p.x, p.y + 2});
    }

    if(!vis[{p.x - 2, p.y}] && check({p.x - 2, p.y})){
        vis[{p.x - 2, p.y}] = true;
        dfs({p.x - 2, p.y});
    }
    if(!vis[{p.x + 2, p.y}] && check({p.x + 2, p.y})){
        vis[{p.x + 2, p.y}] = true;
        dfs({p.x + 2, p.y});
    }
    if(!vis[{p.x, p.y - 2}] && check({p.x, p.y - 2})){
        vis[{p.x, p.y - 2}] = true;
        dfs({p.x, p.y - 2});
    }
    if(!vis[{p.x, p.y + 2}] && check({p.x, p.y + 2})){
        vis[{p.x, p.y + 2}] = true;
        dfs({p.x, p.y + 2});
    }
}

int construct_roads(vector<int> xvec, vector<int> yvec){
    int n = xvec.size();
 
    dsu.reset(n);
 
    for(int i = 0; i < n; i++) nodes[{xvec[i], yvec[i]}] = i;
 
    if(*max_element(xvec.begin(), xvec.end()) <= 2){    // subtask 1
        for(auto p : nodes){
            Point po = p.first;
            if(nodes.find({2, po.y + 2}) != nodes.end()){
                edges[{p.second, nodes[{2, po.y + 2}]}] = {1, po.y + 1};
                dsu.setunion(p.second, nodes[{2, po.y + 2}]);
            }
        }
    }
    else if(*max_element(xvec.begin(), xvec.end()) <= 4){    // subtask 2
        vector<int> x2, x4;
 
        for(int i = 0; i < n; i++){
            if(xvec[i] == 2) x2.push_back(yvec[i]);
            else if(xvec[i] == 4) x4.push_back(yvec[i]);
        } 
 
        sort(x2.begin(), x2.end());
        sort(x4.begin(), x4.end());
 
        for(auto y : x2){
            if(nodes.find({2, y + 2}) != nodes.end()){
                edges[{nodes[{2, y}], nodes[{2, y + 2}]}] = {1, y + 1};
                dsu.setunion(nodes[{2, y}], nodes[{2, y + 2}]);
            }
        }
 
        for(auto y : x4){
            if(nodes.find({4, y + 2}) != nodes.end()){
                edges[{nodes[{4, y}], nodes[{4, y + 2}]}] = {5, y + 1};
                dsu.setunion(nodes[{4, y}], nodes[{4, y + 2}]);
            }
 
            if(nodes.find({2, y}) != nodes.end()){
                edges[{nodes[{4, y}], nodes[{2, y}]}] = {3, y + 1};
                dsu.setunion(nodes[{4, y}], nodes[{2, y}]);
            }
        }
    }
    else if(*max_element(xvec.begin(), xvec.end()) <= 6){    // subtask 3
        vector<int> x2, x4, x6;
 
        for(int i = 0; i < n; i++){
            if(xvec[i] == 2) x2.push_back(yvec[i]);
            else if(xvec[i] == 4) x4.push_back(yvec[i]);
            else if(xvec[i] == 6) x6.push_back(yvec[i]);
        } 
 
        sort(x2.begin(), x2.end());
        sort(x4.begin(), x4.end());
        sort(x6.begin(), x6.end());
 
        for(auto y : x2){
            if(nodes.find({2, y + 2}) != nodes.end()){
                edges[{nodes[{2, y}], nodes[{2, y + 2}]}] = {1, y + 1};
                dsu.setunion(nodes[{2, y}], nodes[{2, y + 2}]);
            }
        }
 
        for(auto y : x6){
            if(nodes.find({6, y + 2}) != nodes.end()){
                edges[{nodes[{6, y}], nodes[{6, y + 2}]}] = {7, y + 1};
                dsu.setunion(nodes[{6, y}], nodes[{6, y + 2}]);
            }
        }
 
        for(auto y : x4){
            if(nodes.find({4, y + 2}) != nodes.end()){
                dsu.setunion(nodes[{4, y}], nodes[{4, y + 2}]);
            }
        }
 
        for(auto y : x4){
            if(nodes.find({6, y}) != nodes.end() && dsu.setfind(nodes[{4, y}]) != dsu.setfind(nodes[{6, y}])){
                edges[{nodes[{4, y}], nodes[{6, y}]}] = {5, y - 1};
                vis[{5, y - 1}] = true;
                dsu.setunion(nodes[{4, y}], nodes[{6, y}]);
 
                if(nodes.find({2, y}) != nodes.end() && dsu.setfind(nodes[{4, y}]) != dsu.setfind(nodes[{2, y}])){
                    edges[{nodes[{2, y}], nodes[{4, y}]}] = {3, y + 1};
                    vis[{3, y + 1}] = true;
                    dsu.setunion(nodes[{2, y}], nodes[{4, y}]);
                }
            }
            else if(nodes.find({2, y}) != nodes.end() && dsu.setfind(nodes[{4, y}]) != dsu.setfind(nodes[{2, y}])){
                edges[{nodes[{2, y}], nodes[{4, y}]}] = {3, y - 1};
                vis[{3, y - 1}] = true;
                dsu.setunion(nodes[{2, y}], nodes[{4, y}]);
            }
        }
 
        for(auto y : x4){
            if(nodes.find({4, y + 2}) != nodes.end()){
                if(!vis[{3, y + 1}]){
                    edges[{nodes[{4, y}], nodes[{4, y + 2}]}] = {3, y + 1};
                }
                else if(!vis[{5, y + 1}]){
                    edges[{nodes[{4, y}], nodes[{4, y + 2}]}] = {5, y + 1};
                }
                // else assert(false);
            }
        }
    }
    else{    // subtask 4, 5
        stack<Point> que;

        Point fpo = nodes.begin()->first;

        if(nodes.find({fpo.x + 2, fpo.y}) != nodes.end()){
            dfs({fpo.x + 1, fpo.y - 1});
        }
        else if(nodes.find({fpo.x, fpo.y + 2}) != nodes.end()){
            dfs({fpo.x - 1, fpo.y + 1});
        }
    }
 
    if(dsu.setcnt == 1){
        vector<int> vecs[4];
 
        for(auto p : edges){
            vecs[0].push_back(p.first.x);
            vecs[1].push_back(p.first.y);
            vecs[2].push_back(p.second.x);
            vecs[3].push_back(p.second.y);
        }
 
        build(vecs[0], vecs[1], vecs[2], vecs[3]);
 
        return 1;
    }
    else return 0;
}

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