Submission #802735

#	Time	Username	Problem	Language	Result	Execution time	Memory
802735		SamAnd	Fountain Parks (IOI21_parks)	C++17	55 / 100	1703 ms	135544 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 400005;

int n;
vector<int> g[N];

bool c[N];
vector<int> uu, vv;
void dfs(int x)
{
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (c[h])
            continue;
        uu.push_back(x);
        vv.push_back(g[x][i]);
        dfs(h);
    }
}

vector<pair<int, int> > rs;
vector<int> gg[N], gi[N];
void dfs(int x, vector<int>& a, vector<int>& b)
{
    c[x] = true;
    for (int i = 0; i < gg[x].size(); ++i)
    {
        int h = gg[x][i];
        if (a[gi[x][i]] == -1)
        {
            a[gi[x][i]] = rs[x].fi;
            b[gi[x][i]] = rs[x].se;
        }
        if (!c[h])
            dfs(h, a, b);
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    std::vector<int> u, v, a, b;

    n = sz(x);
    vector<pair<int, int> > p;
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; ++i)
    {
        p.push_back(m_p(x[i], y[i]));
        mp[m_p(x[i], y[i])] = i;
    }

    int z = 0;
    map<pair<int, int>, int> s;
    for (int i = 0; i < n; ++i)
    {
        int x = p[i].fi;
        int y = p[i].se;
        if (mp.find(m_p(x + 2, y)) != mp.end())
        {
            u.push_back(mp[m_p(x, y)]);
            v.push_back(mp[m_p(x + 2, y)]);
            if (s.find(m_p(x + 1, y + 1)) == s.end())
                s[m_p(x + 1, y + 1)] = z++;
            if (s.find(m_p(x + 1, y - 1)) == s.end())
                s[m_p(x + 1, y - 1)] = z++;
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
            gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x + 1, y - 1)]);
            gg[s[m_p(x + 1, y - 1)]].push_back(s[m_p(x + 1, y + 1)]);
            gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
            gi[s[m_p(x + 1, y - 1)]].push_back(sz(u) - 1);
        }
        if (mp.find(m_p(x, y + 2)) != mp.end())
        {
            u.push_back(mp[m_p(x, y)]);
            v.push_back(mp[m_p(x, y + 2)]);
            if (s.find(m_p(x + 1, y + 1)) == s.end())
                s[m_p(x + 1, y + 1)] = z++;
            if (s.find(m_p(x - 1, y + 1)) == s.end())
                s[m_p(x - 1, y + 1)] = z++;
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
            gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x - 1, y + 1)]);
            gg[s[m_p(x - 1, y + 1)]].push_back(s[m_p(x + 1, y + 1)]);
            gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
            gi[s[m_p(x - 1, y + 1)]].push_back(sz(u) - 1);
        }
    }

    rs.assign(z, m_p(0, 0));
    for (auto it = s.begin(); it != s.end(); ++it)
    {
        rs[it->se] = it->fi;
    }

    dfs(0);
    for (int i = 0; i < n; ++i)
    {
        if (!c[i])
            return 0;
    }

    int maxu = 0;
    for (int i = 0; i < n; ++i)
    {
        maxu = max(maxu, x[i]);
    }

    memset(c, false, sizeof c);
    a.assign(sz(u), -1);
    b.assign(sz(u), -1);

    if (maxu <= 6)
    {
        u = uu;
        v = vv;
        a.assign(sz(u), -1);
        b.assign(sz(u), -1);
        vector<pair<pair<int, int>, int> > p;
        for (int i = 0; i < sz(u); ++i)
        {
            int mx = (x[u[i]] + x[v[i]]) / 2;
            int my = (y[u[i]] + y[v[i]]) / 2;
            p.push_back(m_p(m_p(my, mx), i));
        }
        sort(all(p));
        for (int i = 0; i < sz(u); ++i)
        {
            uu[i] = u[p[i].se];
            vv[i] = v[p[i].se];
        }
        u = uu;
        v = vv;
        for (int i = 0; i < sz(u); ++i)
        {
            int mx = (x[u[i]] + x[v[i]]) / 2;
            int my = (y[u[i]] + y[v[i]]) / 2;
            if (mx % 2 == 0)
            {
                if (!c[s[m_p(mx - 1, my)]])
                {
                    a[i] = mx - 1;
                    b[i] = my;
                    c[s[m_p(mx - 1, my)]] = true;
                }
                else
                {
                    assert(!c[s[m_p(mx + 1, my)]]);
                    a[i] = mx + 1;
                    b[i] = my;
                    c[s[m_p(mx + 1, my)]] = true;
                }
            }
            else
            {
                assert(my % 2 == 0);
                if (!c[s[m_p(mx, my - 1)]])
                {
                    a[i] = mx;
                    b[i] = my - 1;
                    c[s[m_p(mx, my - 1)]] = true;
                }
                else
                {
                    assert(!c[s[m_p(mx, my + 1)]]);
                    a[i] = mx;
                    b[i] = my + 1;
                    c[s[m_p(mx, my + 1)]] = true;
                }
            }
        }
    }
    else
    {
        for (int i = 0; i < z; ++i)
        {
            if (!c[i] && sz(gg[i]) == 1)
            {
                dfs(i, a, b);
            }
        }
        for (int i = 0; i < z; ++i)
        {
            if (!c[i])
            {
                dfs(i, a, b);
            }
        }
    }

    build(u, v, a, b);
    return 1;
}

/*
3
2 2
4 4
2 4

3
2 2
4 2
2 4

3
4 2
2 2
4 4

3
4 4
4 2
2 4

9
4 2
4 4
2 2
2 4
2 6
4 6
2 8
4 8
4 10
*/

Compilation message (stderr)

parks.cpp: In function 'void dfs(int)':
parks.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
parks.cpp: In function 'void dfs(int, std::vector<int>&, std::vector<int>&)':
parks.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < gg[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~

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