Submission #436040

#	Time	Username	Problem	Language	Result	Execution time	Memory
436040		CodePlatina	Fountain Parks (IOI21_parks)	C++17	15 / 100	216 ms	36940 KiB

parks

#include "parks.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#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;

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});
    }

    for(int i = 0; i < 202020; ++i) par[i] = i;

    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;

    for(auto [i, j] : tr)
    {
        if(x[i] == x[j])
        {
            if(x[i] == 2) U.push_back(i), V.push_back(j), A.push_back(1), B.push_back(y[i] + 1);
            else U.push_back(i), V.push_back(j), A.push_back(5), B.push_back(y[i] + 1);
        }
        else U.push_back(i), V.push_back(j), A.push_back(3), B.push_back(y[i] + 1);
    }

    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:43:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     if(tr.size() != n - 1) return 0;
      |        ~~~~~~~~~~^~~~~~~~

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