Submission #1023178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023178		NeroZein	Fountain Parks (IOI21_parks)	C++17	30 / 100	376 ms	47528 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std; 

const int N = 2e5 + 5;

int p[N];
int sz[N];
vector<pair<int, int>> inY[N];

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v]));
}

void unite(int u, int v) {
  u = get(u);
  v = get(v);
  if (sz[u] > sz[v]) swap(u, v);
  p[u] = v;
  sz[v] += sz[u];
}

int construct_roads(vector<int> vx, vector<int> vy) {
  int n = (int) vx.size();
  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    sz[i] = 1;
    mp[{vx[i], vy[i]}] = i;
    inY[vy[i]].emplace_back(vx[i], i); 
  }
  for (int y = 2; y < N; y += 2) {
    sort(inY[y].begin(), inY[y].end());
  }
  set<pair<int, int>> se; 
  vector<int> u, v, a, b;
  for (int y = 2; y < N; y += 2) {
    for (auto [x, i] : inY[y]) {
      if (mp.count({x + 2, y})) {
        int id = mp[{x + 2, y}];
        if (get(id) != get(i)) {
          unite(i, id); 
          u.push_back(i);
          v.push_back(id);
          if (!se.count({x + 1, y - 1})) {
            se.insert({x + 1, y - 1});
            a.push_back(x + 1);
            b.push_back(y - 1);
          } else {
            assert(!se.count({x + 1, y + 1}));
            se.insert({x + 1, y + 1});
            a.push_back(x + 1);
            b.push_back(y + 1); 
          }
        }
      }
      if (mp.count({x, y + 2})) {
        int id = mp[{x, y + 2}];
        if (get(id) != get(i)) {
          unite(i, id);
          u.push_back(i);
          v.push_back(id);
          if (!se.count({x - 1, y + 1})) {
            se.insert({x - 1, y + 1});
            a.push_back(x - 1);
            b.push_back(y + 1); 
          } else {
            assert(!se.count({x + 1, y + 1}));
            se.insert({x + 1, y + 1});
            a.push_back(x + 1);
            b.push_back(y + 1);
          }
        }
      }
    }
  }
  if (sz[get(0)] != n) {
    return 0;
  }
  build(u, v, a, b); 
  return 1;
}

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