Submission #435621

#	Time	Username	Problem	Language	Result	Execution time	Memory
435621		prvocislo	Fountain Parks (IOI21_parks)	C++17	100 / 100	1632 ms	65476 KiB

parks

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

const int maxn = 2e5 + 5;
vector<vector<int> > g(maxn);
vector<int> sz(maxn, 0);
int dfs(int u)
{
    sz[u] = 1;
    for (int v : g[u]) if (!sz[v]) sz[u] += dfs(v);
    return sz[u];
}
int construct_roads(vector<int> x, vector<int> y)
{
    map<pair<int, int>, int> m;
    int n = x.size();
    for (int i = 0; i < n; i++)
        m[{x[i], y[i]}] = i;
    set<pair<int, int> > s;
    for (int i = 0; i < n; i++)
    {
        if (m.count({x[i], y[i] + 2}))
        {
            int j = m[{x[i], y[i]+2}];
            g[i].push_back(j), g[j].push_back(i);
            s.insert({x[i]+1, y[i]+1}), s.insert({x[i]-1, y[i]+1});
        }
        if (m.count({x[i] + 2, y[i]}))
        {
            int j = m[{x[i]+2, y[i]}];
            g[i].push_back(j), g[j].push_back(i);
            s.insert({x[i]+1, y[i]+1}), s.insert({x[i]+1, y[i]-1});
        }
    }
    vector<int> u, v, a, b;
    if (dfs(0) != n) return 0;
    for (pair<int, int> i : s)
    {
        int x = i.first, y = i.second;
        bool updown = ((x^y)&2);
        pair<int, int> p1, p2, q1, q2;
        if (updown) // horizontalne ciary - y sa nemeni
        {
            p1 = {x-1, y-1}, p2 = {x+1, y-1};
            q1 = {x-1, y+1}, q2 = {x+1, y+1};
        }
        else
        {
            p1 = {x-1, y-1}, p2 = {x-1, y+1};
            q1 = {x+1, y-1}, q2 = {x+1, y+1};
        }
        if (m.count(p1) && m.count(p2))
            u.push_back(m[p1]), v.push_back(m[p2]), a.push_back(x), b.push_back(y);
        else if (m.count(q1) && m.count(q2))
            u.push_back(m[q1]), v.push_back(m[q2]), a.push_back(x), b.push_back(y);
    }
    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: 30 / 30