Submission #560694

#	Time	Username	Problem	Language	Result	Execution time	Memory
560694		AlperenT	Fountain Parks (IOI21_parks)	C++17	30 / 100	674 ms	51212 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(x == sc.x) return y < sc.y;
        else return x < sc.x;
    }
};
 
int construct_roads(vector<int> xvec, vector<int> yvec){
    int n = xvec.size();
 
    dsu.reset(n);
 
    map<Point, int> nodes;
    map<Point, Point> edges;
    map<Point, bool> vis;
 
    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
        for(auto p : nodes){
            Point po = p.first;

            if(nodes.find({po.x + 2, po.y}) != nodes.end()){
                if(!vis[{po.x + 1, po.y - 1}]){
                    edges[{p.second, nodes[{po.x + 2, po.y}]}] = {po.x + 1, po.y - 1};
                    vis[{po.x + 1, po.y - 1}] = true;
                }
                else if(!vis[{po.x + 1, po.y + 1}]){
                    edges[{p.second, nodes[{po.x + 2, po.y}]}] = {po.x + 1, po.y + 1};
                    vis[{po.x + 1, po.y + 1}] = true;
                }
                else assert(false);
            }

            if(nodes.find({po.x, po.y + 2}) != nodes.end()){
                if(!vis[{po.x + 1, po.y + 1}]){
                    edges[{p.second, nodes[{po.x, po.y + 2}]}] = {po.x + 1, po.y + 1};
                    vis[{po.x + 1, po.y + 1}] = true;
                }
                else if(!vis[{po.x - 1, po.y + 1}]){
                    edges[{p.second, nodes[{po.x, po.y + 2}]}] = {po.x - 1, po.y + 1};
                    vis[{po.x - 1, po.y + 1}] = true;
                }
                else assert(false);
            }
        }
    }
 
    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: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30