Submission #802386

#	Time	Username	Problem	Language	Result	Execution time	Memory
802386		SamAnd	Fountain Parks (IOI21_parks)	C++17	15 / 100	524 ms	66296 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 = 200005;

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

bool c[N];
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;
        dfs(h);
    }
}

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;
    }
    sort(all(p));
    set<pair<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())
            {
                a.push_back(x + 1);
                b.push_back(y + 1);
            }
            else if (s.find(m_p(x + 1, y - 1)) == s.end())
            {
                a.push_back(x + 1);
                b.push_back(y - 1);
            }
            else
            {
                assert(false);
            }
            s.insert(m_p(a.back(), b.back()));
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
        }
        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())
            {
                a.push_back(x + 1);
                b.push_back(y + 1);
            }
            else if (s.find(m_p(x - 1, y + 1)) == s.end())
            {
                a.push_back(x - 1);
                b.push_back(y + 1);
            }
            else
            {
                assert(false);
            }
            s.insert(m_p(a.back(), b.back()));
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
        }
    }

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

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

Compilation message (stderr)

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

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