Submission #1020679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020679		NeroZein	Fountain Parks (IOI21_parks)	C++17	30 / 100	459 ms	69816 KiB

parks

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

using namespace std; 

const int MAXY = 2e5 + 5; 

map<pair<int, int>, int> mp;
vector<pair<int, int>> inY[MAXY];

int construct_roads(vector<int> x, vector<int> y) {
  int n = (int) x.size();
  for (int i = 0; i < n; ++i) {
    inY[y[i]].emplace_back(x[i], i); 
    mp[{x[i], y[i]}] = i;
  }
  set<pair<int, int>> se;
  vector<int> u, v, a, b;
  vector<vector<int>> g(n); 
  auto addedge = [&](int uu, int vv, int aa, int bb) {
    u.push_back(uu);
    v.push_back(vv);
    a.push_back(aa);
    b.push_back(bb);
    g[uu].push_back(vv);
    g[vv].push_back(uu);
    se.insert({aa, bb}); 
    //cout << "u, v, a, b: " << uu << ' ' << vv << ' ' << aa << ' ' << bb << '\n'; 
  };
  for (int cury = 2; cury < MAXY; cury += 2) {//add vertical lines
    int cnt = 0;
    sort(inY[cury].begin(), inY[cury].end());
    for (int j = 0; j < (int) inY[cury].size(); ++j) {
      auto [curx, id] = inY[cury][j];
      if (mp.count({curx, cury + 2})) {
        cnt++; 
      }
    }
    for (int j = 0; j < (int) inY[cury].size(); ++j) {
      auto [curx, id] = inY[cury][j];
      if (!mp.count({curx, cury + 2})) {
        continue; 
      }
      if (curx == 2) {
        addedge(id, mp[{curx, cury + 2}], curx - 1, cury + 1);
      } else if (curx == 6) {
        addedge(id, mp[{curx, cury + 2}], curx + 1, cury + 1);
      } else if (cnt == 1) {
        addedge(id, mp[{curx, cury + 2}], curx + (cury % 4 == 0 ? -1 : 1), cury + 1);
      }
    }
  }
  for (int cury = 2; cury < MAXY; cury += 2) {//add horizontal lines (x, y) -> (x + 2, y)
    for (int j = 0; j < (int) inY[cury].size() - 1; ++j) {
      auto [curx, id] = inY[cury][j];
      if (inY[cury][j + 1].first - curx > 2) continue; 
      if (se.count({curx + 1, cury - 1})) {
        addedge(id, inY[cury][j + 1].second, curx + 1, cury + 1);
      } else {
        addedge(id, inY[cury][j + 1].second, curx + 1, cury - 1);
      }
    }
  }
  vector<bool> vis(n);
  function<void(int)> dfs = [&](int nd) {
    vis[nd] = true;
    for (int ch : g[nd]) {
      if (!vis[ch]) {
        dfs(ch);        
      }
    }
  };
  dfs(0); 
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) {
      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