Submission #809067

#	Time	Username	Problem	Language	Result	Execution time	Memory
809067		puppy	Fountain Parks (IOI21_parks)	C++17	0 / 100	2 ms	1364 KiB

parks

#include "parks.h"
#include <vector>
using namespace std;
int coord[3][100005];
bool bench[4][100005];
struct UnionFind
{
    vector<int> par;
    UnionFind(int N)
    {
        par.resize(N+1);
        for (int i = 0; i <= N; i++) par[i] = i;
    }
    int fin(int v)
    {
        return v == par[v] ? v : (par[v] = fin(par[v]));
    }
    void uni(int u, int v)
    {
        par[fin(u)] = fin(v);
    }
    bool isuni(int u, int v)
    {
        return fin(u) == fin(v);
    }
};

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int N = x.size();
    fill(&coord[0][0], &coord[2][100005], -1);
    for (int i = 0; i < N; i++) {
        coord[(x[i]-2)/2][y[i]/2] = i;
    }
    UnionFind uf(N);
    vector<int> u, v, a, b;
    for (int i = 1; i < 100000; i++) {
        if (coord[0][i] != -1 && coord[0][i+1] != -1) {
            uf.uni(coord[0][i], coord[0][i+1]);
            u.push_back(coord[0][i]);
            v.push_back(coord[0][i+1]);
            a.push_back(1);
            b.push_back(2*i+1);
        }
        if (coord[2][i] != -1 && coord[2][i+1] != -1) {
            uf.uni(coord[2][i], coord[2][i+1]);
            u.push_back(coord[2][i]);
            v.push_back(coord[2][i+1]);
            a.push_back(7);
            b.push_back(2*i+1);
        }
    }
    vector<pair<int, int>> edge;
    for (int i = 1; i <= 100000; i++) {
        if (coord[0][i] != -1 && coord[1][i] != -1) {
            uf.uni(coord[0][i], coord[1][i]);
            edge.push_back(make_pair(coord[0][i], coord[1][i]));
        }
        if (coord[1][i] != -1 && coord[2][i] != -1) {
            uf.uni(coord[1][i], coord[2][i]);
            edge.push_back(make_pair(coord[1][i], coord[2][i]));
        }
    }
    bool flag = false;
    for (int i = 1; i < 100000; i++) {
        if (coord[1][i] != -1 && coord[1][i+1] != -1) {
            if (uf.isuni(coord[1][i], coord[1][i+1])) continue;
            uf.uni(coord[1][i], coord[1][i+1]);
            u.push_back(coord[1][i]);
            v.push_back(coord[1][i+1]);
            b.push_back(2*i+1);
            if (!flag) a.push_back(3);
            else a.push_back(5);
            bench[a.back()/2][b.back()/2] = true;
            flag = !flag;
        }
    }
    for (pair<int, int> p:edge) {
        u.push_back(p.first);
        v.push_back(p.second);
        int xc = x[p.first] + x[p.second] >> 1;
        int yc = y[p.first];
        a.push_back(xc);
        if (bench[xc/2][(yc+1)/2]) b.push_back(yc-1);
        else b.push_back(yc+1);
        bench[a.back()/2][b.back()/2] = true;
    }
    build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:80:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int xc = x[p.first] + x[p.second] >> 1;

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