Submission #1198759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198759		abczz	Fountain Parks (IOI21_parks)	C++17	55 / 100	593 ms	84728 KiB

parks

#include "parks.h"
#include <iostream>
#include <map>
#include <array>
#define ll long long

using namespace std;

map <array<ll, 2>, ll> mp;
map <array<ll, 2>, array<ll, 2>> mp2;
vector <ll> adj[200000];
bool visited[200000];
ll dj[4][2] = {0, 2, 0, -2, 2, 0, -2, 0}, X[200000], Y[200000];

void dfs(ll u, ll dir) {
  visited[u] = 1;
  for (auto v : adj[u]) {
    if (visited[v]) continue;
    ll a = (X[u]+X[v])/2+(Y[v]-Y[u])/2 * dir;
    ll b = (Y[u]+Y[v])/2+(X[u]-X[v])/2 * dir;
    if (!mp2.count({a, b})) {
      mp2[{a, b}] = {u, v};
      dfs(v, -dir);
    }
  }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
  mp.clear();
  mp2.clear();
  for (int i=0; i<x.size(); ++i) {
    X[i] = x[i], Y[i] = y[i];
    visited[i] = 0;
    adj[i].clear();
    mp[{x[i], y[i]}] = i;
  }
  for (int i=0; i<x.size(); ++i) {
    for (int j=0; j<4; ++j) {
      ll nx = x[i] + dj[j][0], ny = y[i] + dj[j][1];
      if (mp.count({nx, ny})) {
        ll a = mp[{x[i], y[i]}];
        ll b = mp[{nx, ny}];
        adj[a].push_back(b);
        adj[b].push_back(a);
      }
    }
  }
  dfs(0, 1);
  vector <int> U, V, A, B;
  if (mp2.size() != (ll)x.size()-1) return 0;
  else {
    auto it = mp2.begin();
    while (it != mp2.end()) {
      U.push_back(it->second[0]);
      V.push_back(it->second[1]);
      A.push_back(it->first[0]);
      B.push_back(it->first[1]);
      it = next(it);
    }
    build(U, V, A, B);
    return 1;
  }
}

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