Submission #439484

#	Time	Username	Problem	Language	Result	Execution time	Memory
439484		qwerasdfzxcl	Fountain Parks (IOI21_parks)	C++17	100 / 100	1042 ms	146924 KiB

parks

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

using namespace std;
typedef long long ll;
struct point{
    int x, y, n;
    point(){}
    point(int _x, int _y, int _n): x(_x), y(_y), n(_n) {}
    bool operator<(const point &P) const{
        if (x+y==P.x+P.y) return y<P.y;
        return x+y<P.x+P.y;
    }
};
struct DSU{
    int path[200200];
    void init(int n){
        for (int i=0;i<n;i++) path[i] = i;
    }
    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }
    void merge(int s, int v){
        int x = find(s), y = find(v);
        if (x==y) return;
        path[x] = y;
    }
}dsu;
struct Vertex{
    int s, e, x, y;
    Vertex(){}
    Vertex(int _s, int _e, int _x, int _y): s(_s), e(_e), x(_x), y(_y) {}
};
map<int, int> mp[200200];
multimap<pair<int, int>, int> INV;
vector<Vertex> graph;
vector<int> adj[400400], inv[400400];

bool make_edge(int x, int y, int x2, int y2){
    if (mp[x].find(y)==mp[x].end() || mp[x2].find(y2)==mp[x2].end()) return 0;
    int tmp1 = mp[x][y], tmp2 = mp[x2][y2];
    if (dsu.find(tmp1)==dsu.find(tmp2)) return 0;
    if (tmp1>tmp2) swap(tmp1, tmp2);
    dsu.merge(tmp1, tmp2);

    if (x==x2){
        graph.emplace_back(tmp1, tmp2, x-1, (y+y2)/2);
        graph.emplace_back(tmp1, tmp2, x+1, (y+y2)/2);
        INV.insert(make_pair(make_pair(x-1, (y+y2)/2), (int)graph.size()-2));
        INV.insert(make_pair(make_pair(x+1, (y+y2)/2), (int)graph.size()-1));
    }
    else{
        graph.emplace_back(tmp1, tmp2, (x+x2)/2, y-1);
        graph.emplace_back(tmp1, tmp2, (x+x2)/2, y+1);
        INV.insert(make_pair(make_pair((x+x2)/2, y-1), (int)graph.size()-2));
        INV.insert(make_pair(make_pair((x+x2)/2, y+1), (int)graph.size()-1));
    }
    return 1;
}

bool valid(int n){
    bool ret = 1;
    for (int i=0;i<n-1;i++) if (dsu.find(i)!=dsu.find(i+1)) ret = 0;
    return ret;
}

int sccnum[400400], col[400400], cnt = 0;
bool visited[400400];
stack<int> st;
vector<vector<int>> scc;

void dfs1(int s){
    visited[s] = 1;
    for (auto &v:adj[s]) if (!visited[v]) dfs1(v);
    st.push(s);
}

void dfs2(int s){
    visited[s] = 1;
    sccnum[s] = cnt;
    scc.back().push_back(s);
    for (auto &v:inv[s]) if (!visited[v]) dfs2(v);
}

void getscc(int n){
    for (int i=0;i<n;i++){
        for (auto &v:adj[i]) inv[v].push_back(i);
    }
    for (int i=0;i<n;i++) if (!visited[i]) dfs1(i);
    fill(visited, visited+n, 0);
    scc.push_back(vector<int>());
    while(!st.empty()){
        int cur = st.top(); st.pop();
        if (visited[cur]) continue;
        cnt++;
        scc.push_back(vector<int>());
        dfs2(cur);
    }
}

bool cmp(point &x, point &y){
    if (x.y==y.y) return x.x<y.x;
    return x.y<y.y;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> ansu, ansv, ansa, ansb;
    vector<point> vec;
    int n = x.size();
    for (int i=0;i<n;i++){
        vec.emplace_back(x[i], y[i], i);
        mp[x[i]][y[i]] = i;
    }

    ///graph modeling
    dsu.init(n);
    sort(vec.begin(), vec.end());
    for (int i=0;i<n;i++) if ((vec[i].x+vec[i].y)%4==2){
        make_edge(vec[i].x, vec[i].y, vec[i].x+2, vec[i].y);
        make_edge(vec[i].x, vec[i].y, vec[i].x, vec[i].y+2);
    }
    for (int i=0;i<n;i++) if ((vec[i].x+vec[i].y)%4==0){
        make_edge(vec[i].x, vec[i].y, vec[i].x+2, vec[i].y);
        make_edge(vec[i].x, vec[i].y, vec[i].x, vec[i].y+2);
    }
    if (!valid(n)) return 0;

    for (auto iter=INV.begin();iter!=INV.end();++iter){
        auto tmp = INV.equal_range(iter->first);
        auto iter1 = tmp.first, iter2 = tmp.second;
        for(;iter1!=iter2;++iter1){
            if (iter1==iter) continue;
            adj[iter->second].push_back((iter1->second)^1);
        }
    }
    ///

    getscc((int)graph.size());
    for (int i=0;i<(int)graph.size();i++) if (sccnum[i]==sccnum[i^1]) return 0;

    ///finding solution
    fill(col, col+(int)graph.size(), -1);
    for (auto &V:scc){
        int tmp = 0;
        for (auto &x:V) if (col[x]==1) tmp = 1;
        for (auto &x:V) col[x] = tmp, col[x^1] = tmp^1;
    }
    ///
    for (int i=0;i<(int)graph.size();i++) if (col[i]==1){
        ansu.push_back(graph[i].s);
        ansv.push_back(graph[i].e);
        ansa.push_back(graph[i].x);
        ansb.push_back(graph[i].y);
    }
    build(ansu, ansv, ansa, ansb);
    return 1;
}

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