Submission #465695

#	Time	Username	Problem	Language	Result	Execution time	Memory
465695		alexxela12345	Fountain Parks (IOI21_parks)	C++17	15 / 100	863 ms	52792 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    map<pair<int, int>, int> byc;
    int n = x.size();
    for (int i = 0; i < n; i++) {
      byc[{x[i], y[i]}] = i;
    }
    vector<int> u, v, a, b;
    vector<vector<int>> g(n);
    auto add = [&](int i, int j) {
      if (i < j) {
	g[i].push_back(j);
	g[j].push_back(i);
        u.push_back(i);
        v.push_back(j);
        if (x[i] != x[j]) {
	  a.push_back((x[i] + x[j]) / 2);
	  b.push_back(y[i] + 1);
        } else {
	  b.push_back((y[i] + y[j]) / 2);
	  if (x[i] == 2) {
	    a.push_back(1);
          } else {
            a.push_back(5);
          }
        }
      }
    };

    for (int i = 0; i < n; i++) {
      {
        pair<int, int> pp = {x[i], y[i]};
        pp.first += 2;
        if (byc.count(pp)) {
          add(i, byc[pp]);
        }
      }
      {
        pair<int, int> pp = {x[i], y[i]};
        pp.second += 2;
        if (byc.count(pp)) {
          add(i, byc[pp]);
        }
      }
      {
        pair<int, int> pp = {x[i], y[i]};
        pp.first -= 2;
        if (byc.count(pp)) {
          add(i, byc[pp]);
        }
      }
      {
        pair<int, int> pp = {x[i], y[i]};
        pp.second -= 2;
        if (byc.count(pp)) {
          add(i, byc[pp]);
        }
      }
    }
    vector<int> used(n);
    function<void(int)> dfs;
    dfs = [&](int v) {
      used[v] = 1;
      for (int u : g[v]) {
        if (!used[u]) {
          dfs(u);
        }
      }
    };
    dfs(0);
    if (*min_element(used.begin(), used.end()) == 0) {
      return 0;
    }
    build(u, v, a, b);
    return 1;
}

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