Submission #1078053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078053		bleahbleah	Fountain Parks (IOI21_parks)	C++17	5 / 100	954 ms	341060 KiB

parks

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

using namespace std;

const int nmax = 2e5 + 5;
using pii = pair<int,int>;
#define sz(x) ((int)(x).size())

map<pii, int> encr;
map<int, pii> decr;
vector<int> g[nmax];
int dirx[4] = {-2, 2, 0, 0}, diry[4] = {0, 0, 2, -2};
int occ[nmax];

vector<pii> edges;
void dfs(int node) {
   occ[node] = 1;
   for(auto x : g[node]) {
      if(occ[x]) continue;
      edges.emplace_back(node, x);
      dfs(x);
   }
   return;
}

pair<vector<int>, vector<int>> unravel(vector<pii>& v) {
   vector<int> a, b;
   for(auto [x, y] : v) a.emplace_back(x), b.emplace_back(y);
   return make_pair(a, b);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
   for(int i = 0; i < sz(x); i++)
      encr[make_pair(x[i], y[i])] = i;
   for(auto [a, b] : encr) {
      decr[b] = a;
      for(int i = 0; i < 4; i++) {
         if(encr.count(make_pair(a.first + dirx[i], a.second + diry[i])))
            g[b].emplace_back(encr[make_pair(a.first + dirx[i], a.second + diry[i])]);
      }
   }
   
   dfs(0);
   if([&]() {
      for(int i = 0; i < sz(x); i++) if(occ[i] == 0) return 1;
      return 0;
   }()) { return 0; }
   
   map<pii, unordered_set<int>> adj;
   vector<pii> avail[5];
   
   for(int i = 0; i < sz(edges); i++) {
      auto [x1, y1] = decr[edges[i].first];
      auto [x2, y2] = decr[edges[i].second];
      if(x1 == x2) {
         adj[make_pair(x1 + 1, max(y1, y2) - 1)].emplace(i);
         adj[make_pair(x1 - 1, max(y1, y2) - 1)].emplace(i);
      }
      else {
         assert(y1 == y2);
         adj[make_pair(max(x1, x2) - 1, y1 - 1)].emplace(i);
         adj[make_pair(max(x1, x2) - 1, y1 + 1)].emplace(i);
      }
   }
   for(auto [a, b] : adj) { avail[sz(b)].emplace_back(a); }
   
   vector<pii> assoc(sz(edges));
   
   auto get_top = [&]() {
      for(int plane = 1; plane <= 4; plane++) {
         while(avail[plane].size()) {
            auto a = avail[plane].back();
            avail[plane].pop_back();
            if(adj.count(a)) return a;
         }
      }
      assert(false);
   };
   
   
   for(int it = 0; it < sz(edges); it++) {
      auto T = get_top();
      //cerr << T.first << ' ' << T.second << '\t';
      int idx = *adj[T].begin(); 
      //cerr << idx << '\n';
      {         
         auto [x1, y1] = decr[edges[idx].first];
         auto [x2, y2] = decr[edges[idx].second];
         if(x1 == x2) {
            auto _1 = make_pair(x1 - 1, max(y1, y2) - 1), _2 = make_pair(x1 + 1, max(y1, y2) - 1);
            adj[_1].erase(idx);
            adj[_2].erase(idx);
            avail[sz(adj[_1])].emplace_back(_1);
            avail[sz(adj[_2])].emplace_back(_2);
         }
         else {
            assert(y1 == y2);
            auto _1 = make_pair(max(x1, x2) - 1, y1 + 1), _2 = make_pair(max(x1, x2) - 1, y1 - 1);
            adj[_1].erase(idx);
            adj[_2].erase(idx);
            avail[sz(adj[_1])].emplace_back(_1);
            avail[sz(adj[_2])].emplace_back(_2);
         }
      }
      
      adj.erase(T);
      assoc[idx] = T;
   }
   
   auto [yi, er] = unravel(edges);
   auto [san, si] = unravel(assoc);
   build(yi, er, san, si);
   return 1;
}

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