Submission #591562

#	Time	Username	Problem	Language	Result	Execution time	Memory
591562		Lucpp	Fountain Parks (IOI21_parks)	C++17	70 / 100	732 ms	99432 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

map<pair<int, int>, int> mp;
vector<bool> vis;
vector<int> dx = {-2, 2, 0, 0};
vector<int> dy = {0, 0, -2, 2};
vector<pair<int, int>> roads;

void dfs(int x, int y){
    int u = mp[make_pair(x, y)];
    for(int i = 0; i < 4; i++){
        int x2 = x+dx[i], y2 = y+dy[i];
        if(mp.count(make_pair(x2, y2))){
            int v = mp[make_pair(x2, y2)];
            if(!vis[v]){
                vis[v] = true;
                dfs(x2, y2);
                roads.emplace_back(u, v);
            }
        }
    }
}

pair<pair<int, int>, pair<int, int>> getBench(int x1, int y1, int x2, int y2){
    if(x1 == x2) return {{x1+1, (y1+y2)/2}, {x1-1, (y1+y2)/2}};
    else return {{(x1+x2)/2, y1+1}, {(x1+x2)/2, y1-1}};
}

vector<vector<int>> g;
vector<int> match;

bool find_path(int u){
    for(int v : g[u]){
        if(!vis[v]){
            vis[v] = true;
            if(match[v] == -1 || find_path(match[v])){
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
    }
    return false;
}

int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    int n = (int)x.size();
    for(int i = 0; i < n; i++){
        mp.emplace(make_pair(x[i], y[i]), i);
    }
    vis.resize(n);
    vis[0] = true;
    dfs(x[0], y[0]);
    for(int i = 0; i < n; i++){
        if(!vis[i]) return 0;
    }
    g.resize(n-1);
    vector<pair<int, int>> benches;
    map<pair<int, int>, int> ind;
    for(int i = 0; i < n-1; i++){
        int u = roads[i].first, v = roads[i].second;
        auto [a, b] = getBench(x[u], y[u], x[v], y[v]);
        if(!ind.count(a)){
            ind[a] = (int)benches.size();
            benches.push_back(a);
        }
        if(!ind.count(b)){
            ind[b] = (int)benches.size();
            benches.push_back(b);
        }
        g[i].push_back(ind[a]+n-1);
        g[i].push_back(ind[b]+n-1);
    }
    int m = n+(int)ind.size();
    match.assign(m, -1);
    int sz = 0;
    while(true){
        int old = sz;
        vis.assign(m, false);
        for(int u = 0; u < n-1; u++){
            if(match[u] == -1) sz += find_path(u);
        }
        if(sz == old) break;
    }
    assert(sz == n-1);

    vector<int> u, v, a, b;
    for(int i = 0; i < n-1; i++){
        u.push_back(roads[i].first);
        v.push_back(roads[i].second);
        a.push_back(benches[match[i]-n+1].first);
        b.push_back(benches[match[i]-n+1].second);
    }
    build(u, v, a, b);
    return 1;
}

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