Submission #987156

#	Time	Username	Problem	Language	Result	Execution time	Memory
987156		cig32	Fountain Parks (IOI21_parks)	C++17	15 / 100	730 ms	53272 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;
  }
  std::vector<int> u, v, a, b;
  map<pair<int, int>, int> mp;
  int n = x.size();
  for(int i=0; i<n; i++) {
    mp[{x[i], y[i]}] = i;
  }
  for(int i=0; i<n; i++) {
    if(mp[{x[i], y[i] + 2}] > i) {
      u.push_back(mp[{x[i], y[i] + 2}]);
      v.push_back(i);
      a.push_back((x[i] == 2 ? 1 : 5));
      b.push_back(y[i] + 1);
    }
    if(mp[{x[i], y[i] - 2}] > i) {
      u.push_back(mp[{x[i], y[i] - 2}]);
      v.push_back(i);
      a.push_back((x[i] == 2 ? 1 : 5));
      b.push_back(y[i] - 1);
    }
    if(mp[{x[i] + 2, y[i]}] > i) {
      u.push_back(mp[{x[i] + 2, y[i]}]);
      v.push_back(i);
      a.push_back(3);
      b.push_back(y[i] - 1);
    }
    if(mp[{x[i] - 2, y[i]}] > i) {
      u.push_back(mp[{x[i] - 2, y[i]}]);
      v.push_back(i);
      a.push_back(3);
      b.push_back(y[i] - 1);
    }
  }
  for(int i=0; i<n; i++) dsu[i] = i;
  for(int i=0; i<u.size(); i++) {
    union_(u[i], v[i]);
  }
  for(int i=1; i<n; i++) if(set_of(i) != set_of(i-1)) return 0;
  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
*/

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0; i<u.size(); i++) {
      |                ~^~~~~~~~~

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