Submission #1059032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059032		qwusha	Fountain Parks (IOI21_parks)	C++17	70 / 100	1029 ms	170344 KiB

parks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ld eps = 1e-8;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const ll inf = 1e18;
const ll mod = 1e9 + 7;

#include "parks.h"


vector<vector<int>> g;
vector<int> u, v, a, b;

vector<int> used;

void dfs(int ver) {
    used[ver] = 1;
    for (auto nod : g[ver]) {
        if (!used[nod]) {
            u.push_back(ver);
            v.push_back(nod);
            dfs(nod);
        }
    }
}



int construct_roads(vector<int> x, vector<int> y) {
    bool fir = 1, sec = 1, thi = 1;
    int n = x.size();
    for (int i = 0; i < n; i++) {
        if (x[i] != 2)
            fir = 0;
    }
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        mp[{x[i], y[i]}] = i;
    }
    g.resize(n);
    for (int i = 0; i < n; i++) {
        if (mp.find({x[i] - 2, y[i]}) != mp.end()) {
            g[i].push_back(mp[{x[i] - 2, y[i]}]);
        }
        if (mp.find({x[i] + 2, y[i]}) != mp.end()) {
            g[i].push_back(mp[{x[i] + 2, y[i]}]);
        }
        if (mp.find({x[i], y[i] - 2}) != mp.end()) {
            g[i].push_back(mp[{x[i], y[i] - 2}]);
        }
        if (mp.find({x[i], y[i] + 2}) != mp.end()) {
            g[i].push_back(mp[{x[i], y[i] + 2}]);
        }
    }
    used.resize(n);
    dfs(0);
    bool ch = 1;
    for (int i = 0; i < n; i++) {
        if (!used[i])
            ch = 0;
    }
    if (!ch)
        return 0;
    map<pair<int, int>, int> bench;
    map<pair<int, int>, set<int>> want;
    set<vector<int>> ben;
    for (int i = 0; i < v.size(); i++) {
        if (x[v[i]] == x[u[i]]) {
            want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].insert(i);
            want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].insert(i);
            bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]++;
            bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]++;
        } else {
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].insert(i);
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].insert(i);
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]++;
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]++;
        }
    }
    for (auto [pa, cnt] : bench) {
        ben.insert({cnt, pa.fi, pa.se});
    }
    a.resize(n - 1);
    b.resize(n - 1);
    set<pair<int, int>> used_ben;
    while(!ben.empty() && used_ben.size() < n - 1) {
        auto cur = *ben.begin();
        int i = *want[{cur[1], cur[2]}].begin();
        a[i] = cur[1];
        b[i] = cur[2];
        used_ben.insert({cur[1], cur[2]});
        if (x[v[i]] == x[u[i]]) {
            want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].erase(i);
            want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].erase(i);
            ben.erase({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2});
            ben.erase({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2});
            bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]--;
            bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]--;
            if (bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}] > 0 && used_ben.find({x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}) == used_ben.end()) {
                ben.insert({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2});
            }
            if (bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}] > 0 && used_ben.find({x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}) == used_ben.end()) {
                ben.insert({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2});
            }
        } else {
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].erase(i);
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].erase(i);
            ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 });
            ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1});
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]--;
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]--;
            if ( bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}] > 0 && used_ben.find({(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}) == used_ben.end()) {
                ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 });
            }
            if (bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}] > 0 && used_ben.find({(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}) == used_ben.end()) {
                ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[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:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
parks.cpp:90:43: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     while(!ben.empty() && used_ben.size() < n - 1) {
      |                           ~~~~~~~~~~~~~~~~^~~~~~~
parks.cpp:34:10: warning: variable 'fir' set but not used [-Wunused-but-set-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |          ^~~
parks.cpp:34:19: warning: unused variable 'sec' [-Wunused-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |                   ^~~
parks.cpp:34:28: warning: unused variable 'thi' [-Wunused-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |                            ^~~

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