Submission #1023273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023273		NeroZein	Fountain Parks (IOI21_parks)	C++17	15 / 100	1775 ms	212660 KiB

parks

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

const int N = 2e5 + 5;

int p[N];
int sz[N];
set<int> se[N];
set<int> to_cross[N];
set<pair<int, int>> from_cross[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;
  }
  for (int i = 0; i < n; ++i) {
    int x = vx[i], y = vy[i];
    for (int dx : {-2, 0, 2}) {
      for (int dy : {-2, 0, 2}) {
        if (dx != 0 && dy != 0) continue; 
        if (mp.count({x + dx, y + dy})) {
          int id = mp[{x + dx, y + dy}];
          if (get(id) != get(i)) {
            unite(i, id);
            se[i].insert(id);
            se[id].insert(i);
          }
        } 
      }
    }
  }
  if (sz[get(1)] != n) {
    return 0; 
  }
  vector<int> u, v, a, b;
  for (int i = 0; i < n; ++i) {
    bool ok = true; 
    int x = vx[i], y = vy[i];
    for (int dx : {-2, 0, 2}) {
      for (int dy : {-2, 0, 2}) {
        if (dx != 0 && dy != 0) continue; 
        ok &= mp.count({x + dx, y + dy});
      }
    }
    if (ok) {
      cout << i << endl; 
      for (int dx : {-2, 2}) {
        int id = mp[{x + dx, y}];
        u.push_back(i);
        v.push_back(id);
        a.push_back(x + dx / 2);
        b.push_back(y + (dx < 0 ? -1 : 1));
        se[id].erase(i);
        se[i].erase(id);
      }
      for (int dy : {-2, 2}) {
        int id = mp[{x, y + dy}];
        u.push_back(i);
        v.push_back(id); 
        a.push_back(x + (dy < 0 ? 1 : -1));
        b.push_back(y + dy / 2);
        se[id].erase(i);
        se[i].erase(id);
      }
    }
  }
  int cnt = 0; 
  vector<int> type;
  vector<set<int>> g;
  map<pair<int, int>, int> crosses;
  map<int, pair<int, int>> lines, bck;
  for (int i = 0; i < n; ++i) {
    int x = vx[i], y = vy[i];
    for (int id : se[i]) {
      if (id < i) continue;
      int xx = vx[id], yy = vy[id];
      int line_id = cnt;
      type.push_back(0);//type[cnt]
      g.push_back({});
      lines[cnt++] = {i, id};
      for (int d : {-1, 1}) {
        int cx, cy;
        if (x == xx) {
          cx = x + d, cy = (y + yy) / 2; 
        } else {
          cx = (x + xx) / 2, cy = y + d;
        }
        if (!crosses.count({cx, cy})) {
          g.push_back({});
          type.push_back(1);
          bck[cnt] = {cx, cy};
          crosses[{cx, cy}] = cnt++;
        }
        int cross_id = crosses[{cx, cy}];
        g[cross_id].insert(line_id);
        g[line_id].insert(cross_id);
      }
    }
  }
  queue<int> que;
  vector<int> indeg(cnt);
  for (int i = 0; i < cnt; ++i) {
    indeg[i] = g[i].size();
    if (g[i].size() == 1) {
      assert(type[i] == 1);
      que.push(i);
    }
  }
  set<int> mentioned;
  while (!que.empty()) {
    int cur = que.front();
    que.pop();
    if (indeg[cur] == 0) {
      continue; 
    }
    //if (type[cur] == 1) {
      //cout << "cross: " << bck[cur].first << ' ' << bck[cur].second << endl; 
    //} else {
      //int i = lines[cur].first, j = lines[cur].second;
      //cout << "line: " << vx[i] << ' ' << vy[i] << ' ' << vx[j] << ' ' << vy[j] << endl; 
    //}
    //assert(indeg[cur] == (int) g[cur].size() && g[cur].size() == 1);
    if (type[cur] == 0) {
      for (int w : g[cur]) {
        g[w].erase(cur);
        --indeg[w];
        if (indeg[w] == 1) {
          que.push(w);
        }
      }
    } else {
      int line_id = *g[cur].begin();
      if (!mentioned.count(line_id)) {
        mentioned.insert(line_id); 
        u.push_back(lines[line_id].first);
        v.push_back(lines[line_id].second);
        a.push_back(bck[cur].first);
        b.push_back(bck[cur].second);        
      }
      for (int w : g[cur]) {
        g[w].erase(cur);
        --indeg[w];
        if (indeg[w] == 1) {
          que.push(w); 
        }
      }
    }
  }
  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