Submission #797809

#	Time	Username	Problem	Language	Result	Execution time	Memory
797809		Liudas	Fountain Parks (IOI21_parks)	C++17	15 / 100	2635 ms	118328 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
vector<vector<int>> new_tree;
void dfs(int head, vector<vector<int>>&tree, vector<int> &vis){
    vis[head] = true;
    for(int i : tree[head]){
        if(!vis[i]){
            new_tree[head].push_back(i);
            new_tree[i].push_back(head);
            dfs(i, tree, vis);
        }
    }
}
int count_benches(vector<int> &c, map<pair<int,int>, int> &taken){
    int s = 2;
    if(c[0] != c[2]){
        s -= taken[{c[0] - (c[0]-c[2])/2, c[1] + 1}];
        s -= taken[{c[0] - (c[0]-c[2])/2, c[1] - 1}];
    }
    else{
        s -= taken[{c[0] + 1, c[1] - (c[1] - c[3]) / 2}];
        s -= taken[{c[0] - 1, c[1] - (c[1] - c[3]) / 2}];
    }
    return s;
}
int construct_roads(vector<int> x, vector<int> y){
    int N = x.size();
    vector<vector<int>> tree(N);
    map<pair<int,int>, int> arr, bench, taken;
    map<array<int, 4>, bool> road;
    for(int i = 0; i < N; i ++){
        arr[{x[i], y[i]}] = i;
    }
    vector<int> dx = {-2, 2, 0, 0}, dy = {0,0,2,-2};
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < 4; j ++){
            if(arr.find({x[i] + dx[j], y[i] + dy[j]}) != arr.end()){
                tree[i].push_back(arr[{x[i] + dx[j], y[i] + dy[j]}]);
            }
        }
    }
    vector<int> vis(N, 0);
    new_tree.resize(N);
    dfs(0, tree, vis);
    tree = new_tree;
    for(int i = 0; i < N; i ++){
        for(int j : tree[i]){
            road[{x[i], y[i], x[j], y[j]}] = true;
            road[{x[j], y[j], x[i], y[i]}] = true;
            if(x[j] != x[i]){
                bench[{(x[i] + x[j])/2, y[i] + 1}] ++;
                bench[{(x[i] + x[j])/2, y[i] - 1}] ++;
            }
            if(y[j] != y[i]){
                bench[{x[i] + 1, (y[i] + y[j]) / 2}] ++;
                bench[{x[i] - 1, (y[i] + y[j]) / 2}] ++;
            }
        }
    }
    vector<pair<int, int>> pairs;
    for(auto [l, r] : bench){
        pairs.push_back(l);
    }
    sort(pairs.begin(), pairs.end(), [&](pair<int, int> a, pair<int, int> b){return bench[a] < bench[b];});
    for(int i : vis){
        if(!i){
            return 0;
        }
    }
    vector<int> ansu, ansv, ansa, ansb;
    for(auto[l ,r] : pairs){
        vector<int> dix = {1, -1, 1, -1}, diy = {-1, 1, 1, -1};
        int bi = -1, bj = -1, s = 1e9;
        for(int i = 0; i < 4; i ++){
            for(int j = 0; j < 4; j ++){
                int ss = 1e9;
                if(road.find({l + dix[i], r + diy[i], l + dix[j], r + diy[j]}) != road.end()){
                    vector<int> tt = {l + dix[i], r + diy[i], l + dix[j], r + diy[j]};
                    ss = count_benches(tt, taken);
                }
                if(s > ss){
                    s = ss;
                    bi = i;
                    bj = j;
                }
            }
        }
        if(bi + 1){
            road.erase({l + dix[bi], r + diy[bi], l + dix[bj], r + diy[bj]});
            road.erase({l + dix[bj], r + diy[bj], l + dix[bi], r + diy[bi]});
            ansu.push_back(arr[{l + dix[bi], r + diy[bi]}]);
            ansv.push_back(arr[{l + dix[bj], r + diy[bj]}]);
            ansa.push_back(l);
            ansb.push_back(r);
            taken[{l, r}] = true;
        }
    }
    build(ansv, ansu, ansa, ansb);
    return 1;
}

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