Submission #987225

#	Time	Username	Problem	Language	Result	Execution time	Memory
987225		cig32	Fountain Parks (IOI21_parks)	C++17	45 / 100	400 ms	58464 KiB

parks

#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 12;
int dsu[MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
    build({}, {}, {}, {});
    return 1;
  }
  int n = x.size();
  pair<pair<int, int>, int> p[n];
  vector<int> stox = x, stoy = y;
  for(int i=0; i<n; i++) {
    p[i].first.first = x[i];
    p[i].first.second = y[i];
    p[i].second = i;
  }
  sort(p, p + n);
  for(int i=0; i<n; i++) x[i] = stox[p[i].second], y[i] = stoy[p[i].second];
  std::vector<int> u, v, a, b;
  map<pair<int, int>, int> mp;
  map<pair<int, int>, pair<int,int> > buh;
  set<pair<int, int>> bench;
  
  for(int i=0; i<n; i++) dsu[i] = i;
  for(int i=0; i<n; i++) {
    mp[{x[i], y[i]}] = i;
  }
  vector<pair<int,int>> edges;
  for(int i=0; i<n; i++) {
    if(mp.count({x[i] + 2, y[i]})) {
      int U = i, V = mp[{x[i] + 2, y[i]}];
      edges.push_back({U, V});
      union_(U, V);
    }
  }
  for(int i=0; i<n; i++) {
    if(mp.count({x[i], y[i] + 2})) {
      int U = i, V = mp[{x[i], y[i] + 2}];
      if(set_of(U) != set_of(V)) {
        edges.push_back({U, V});
        union_(U, V);
        if((x[i] + y[i]) % 4 == 2) {
          bench.insert({x[i] - 1, y[i] + 1});
          buh[{U, V}] = {x[i] - 1, y[i] + 1};
        }
        else {
          bench.insert({x[i] + 1, y[i] + 1});
          buh[{U, V}] = {x[i] + 1, y[i] + 1};
        }
      }
    }
  }
  for(int i=0; i<n; i++) {
    if(mp.count({x[i] + 2, y[i]})) {
      int U = i, V = mp[{x[i] + 2, y[i]}];
      if(!bench.count({x[i] + 1, y[i] - 1})) {
        bench.insert({x[i] + 1, y[i] - 1});
        buh[{U, V}] = {x[i] + 1, y[i] - 1};
      }
      else if(!bench.count({x[i] + 1, y[i] + 1})) {
        bench.insert({x[i] + 1, y[i] + 1});
        buh[{U, V}] = {x[i] + 1, y[i] + 1};
      }
      else return 0;
    }
  }
  for(int i=1; i<n; i++) if(set_of(i) != set_of(i-1)) return 0;
  for(auto x: edges) {
    int U = x.first, V = x.second;
    u.push_back(p[U].second);
    v.push_back(p[V].second);
    pair<int, int> wow = buh[{U, V}];
    a.push_back(wow.first);
    b.push_back(wow.second);
  }
  build(u, v, a, b);
  return 1;
}

/*

#!/bin/bash

problem=parks
grader_name=grady

g++ -std=c++17 -O2 -o "${problem}" "${grader_name}.cpp" "${problem}.cpp"
./parks < input.txt
*/

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