Submission #436227

#	Time	Username	Problem	Language	Result	Execution time	Memory
436227		CodePlatina	Fountain Parks (IOI21_parks)	C++17	55 / 100	3582 ms	93896 KiB

parks

#include "parks.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <random>
#include <chrono>
#define pii pair<int, int>
#define ff first
#define ss second

using namespace std;

const int INF = 202020;
vector<pii> lsX[INF];
vector<pii> lsY[INF];
vector<pii> eg, tr;
int par[202020];
int fnd(int x) { return x == par[x] ? x : par[x] = fnd(par[x]); }
void uni(int x, int y) { par[fnd(x)] = fnd(y); }
vector<int> U, V, A, B;

vector<int> gph[404040];
int ord[404040];
int scc[404040];
int scnt = 0, cnt = 0;
vector<int> S;
int dfs(int x, int p)
{
    int ret = ord[x] = ++cnt;
    S.push_back(x);
    for(int y : gph[x]) if(y != p)
    {
        if(!ord[y]) ret = min(ret, dfs(y, x));
        else if(!scc[y]) ret = min(ret, ord[y]);
    }
    if(ret >= ord[x])
    {
        ++scnt;
        while(S.back() != x) scc[S.back()] = scnt, S.pop_back();
        scc[S.back()] = scnt, S.pop_back();
    }
    return ret;
}

int construct_roads(vector<int> x, vector<int> y)
{
    int n = x.size();
    for(int i = 0; i < n; ++i) lsX[x[i]].push_back({y[i], i});
    for(int i = 0; i < n; ++i) lsY[y[i]].push_back({x[i], i});

    for(int i = 0; i < INF; ++i)
    {
        sort(lsX[i].begin(), lsX[i].end());
        for(int j = 0; j < (int)lsX[i].size() - 1; ++j)
            if(lsX[i][j + 1].ff - lsX[i][j].ff == 2) eg.push_back({lsX[i][j].ss, lsX[i][j + 1].ss});
    }
    for(int i = 0; i < INF; ++i)
    {
        sort(lsY[i].begin(), lsY[i].end());
        for(int j = 0; j < (int)lsY[i].size() - 1; ++j)
            if(lsY[i][j + 1].ff - lsY[i][j].ff == 2) eg.push_back({lsY[i][j].ss, lsY[i][j + 1].ss});
    }

    unsigned seed = chrono::steady_clock::now().time_since_epoch().count();
    mt19937 rng(seed);

    for(int cs = 0; cs < 30; ++cs)
    {
        shuffle(eg.begin(), eg.end(), rng);
        for(int i = 0; i < 202020; ++i) par[i] = i;
        tr.clear();

        for(auto i : eg) if(fnd(i.ff) != fnd(i.ss)) tr.push_back(i), uni(i.ff, i.ss);
        if(tr.size() != n - 1) return 0;

        pii C[n - 1], D[n - 1];
        vector<pii> pr;
        int c = 0;
        for(auto [i, j] : tr)
        {
            if(x[i] == x[j])
            {
                C[c] = {x[i] - 1, y[i] + 1};
                D[c] = {x[i] + 1, y[i] + 1};
            }
            else
            {
                C[c] = {x[i] + 1, y[i] - 1};
                D[c] = {x[i] + 1, y[i] + 1};
            }
            pr.push_back(C[c]);
            pr.push_back(D[c]);
            ++c;
        }

        sort(pr.begin(), pr.end());
        pr.resize(unique(pr.begin(), pr.end()) - pr.begin());
        int E[n - 1], F[n - 1];
        for(int i = 0; i < n - 1; ++i) E[i] = lower_bound(pr.begin(), pr.end(), C[i]) - pr.begin();
        for(int i = 0; i < n - 1; ++i) F[i] = lower_bound(pr.begin(), pr.end(), D[i]) - pr.begin();

        int N = pr.size();
        vector<pii> ls[N];
        for(int i = 0; i < n - 1; ++i) ls[E[i]].push_back({i, 0});
        for(int i = 0; i < n - 1; ++i) ls[F[i]].push_back({i, 1});

        cnt = scnt = 0;
        for(int i = 0; i < 2 * n; ++i) gph[i].clear(), ord[i] = scc[i] = 0;
        S.clear();

        for(int i = 0; i < N; ++i)
        {
            int sz = ls[i].size();
            for(int j = 0; j < sz; ++j)
            {
                for(int k = 0; k < sz; ++k)
                {
                    if(j != k)
                    {
                        int p = ls[i][j].ff + ls[i][j].ss * n;
                        int q = ls[i][k].ff + (!ls[i][k].ss) * n;
                        gph[p].push_back(q);
                    }
                }
            }
        }

        for(int i = 0; i < 2 * n; ++i) if(!ord[i]) dfs(i, -1);

        bool flag = true;
        for(int i = 0; i < n - 1; ++i) if(scc[i] == scc[i + n]) flag = false;
        if(!flag) continue;

        for(int i = 0; i < n - 1; ++i)
        {
            U.push_back(tr[i].ff);
            V.push_back(tr[i].ss);
            if(scc[i] < scc[i + n])
            {
                A.push_back(C[i].ff);
                B.push_back(C[i].ss);
            }
            else
            {
                A.push_back(D[i].ff);
                B.push_back(D[i].ss);
            }
        }

        build(U, V, A, B);
        return 1;
    }

    return 0;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:75:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |         if(tr.size() != n - 1) return 0;
      |            ~~~~~~~~~~^~~~~~~~

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