Submission #525163

#	Time	Username	Problem	Language	Result	Execution time	Memory
525163		vijay	Park (BOI16_park)	C++17	0 / 100	0 ms	204 KiB

park

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;

#define trav(a, x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second

struct DSU {
	vector<int> e;
	DSU(int N) { e = vector<int>(N, -1); }

	// get representive component (uses path compression)
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }

	bool same_set(int a, int b) { return get(a) == get(b); }

	int size(int x) { return -e[get(x)]; }

	bool unite(int x, int y) {  // union by size
		x = get(x), y = get(y);
		if (x == y) return false;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y]; e[y] = x;
		return true;
	}
};

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  ifstream cin;
  // cin.open("test.in");

  int n, m; cin >> n >> m;
  int w, h; cin >> w >> h;

  vector<pair<int, pair<ll, ll> > > trees;
  for(int i = 0; i < n; i++){
    int x, y, radius; cin >> x >> y >> radius;
    trees.pb(mp(radius, mp(x, y)));
  }

  vector<pair<int, pair<ll, int> > > visitors;
  for(int i = 0; i < m; i++){
    int radius, entrance; cin >> radius >> entrance;
    visitors.pb(mp(radius, mp(entrance, i)));
  }

  sort(visitors.begin(), visitors.end());

  // edge codes: left: n, right: n + 1, bottom: n + 2, top: n + 3

  // edges
  vector<pair<double, pair<int, int> > > edges;
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      double dist = sqrt(pow(trees[i].s.f - trees[j].s.f, 2) + pow(trees[i].s.s - trees[j].s.s, 2)) - trees[i].f - trees[j].f;
      edges.pb(mp(dist, mp(i, j)));
    }
    // how to figure out the distance between the edges of the share itself
    edges.pb(mp(trees[i].s.f - trees[i].f, mp(i, n)));
    edges.pb(mp(w - trees[i].s.f - trees[i].f, mp(i, n + 1)));
    edges.pb(mp(trees[i].s.s - trees[i].f, mp(i, n + 2)));
    edges.pb(mp(h - trees[i].s.s - trees[i].f, mp(i, n + 3)));
  }

  sort(edges.begin(), edges.end());

  // for(auto& edge: edges){
  //   if(edge.s.s == n){
  //     cout << edge.f << " " << edge.s.f << " " << edge.s.s << "\n";
  //   }
  // }

  vector<string> ans(m);

  int left = n; int right = n + 1; int bottom = n + 2; int top = n + 3;

  DSU dsu(n + 5);

  int edgesIndex = 0;
  for(int i = 0; i < m; i++){
    while(true){
      dsu.unite(edges[edgesIndex].s.f, edges[edgesIndex].s.s);
      // cout << "uniting " << edges[edgesIndex].s.f << " " << edges[edgesIndex].s.s << " with value " << 2*visitors[i].f << "\n";
      edgesIndex++;

      if(edgesIndex == edges.size() || edges[edgesIndex].f > 2*visitors[i].f){
        // cout << "     break " << edges[edgesIndex].f << " " << visitors[i].f << "\n";
        break;
      }
    }
    // cout << "EDGE " << edgesIndex << " " << edges[edgesIndex].f << " " << visitors[i].f << "\n";
    // which ones should work for this?
    string output = "";

    if(visitors[i].s.f == 1){
      output += "1";
      if(!dsu.same_set(left, bottom) && !dsu.same_set(bottom, right) && !dsu.same_set(bottom, top)){
        output += "2";
      }
      if(!dsu.same_set(left, bottom) && !dsu.same_set(top, right) && !dsu.same_set(left, right)){
        output += "3";
      }
      if(!dsu.same_set(left, bottom) && !dsu.same_set(top, left) && !dsu.same_set(left, right)){
        output += "4";
      }
      // cout << dsu.same_set(left, bottom) << dsu.same_set(top, left) << dsu.same_set(bottom, top) << "\n";
    } else if (visitors[i].s.f == 2){
      if(!dsu.same_set(bottom, right) && !dsu.same_set(bottom, top) && !dsu.same_set(left, bottom)){
        output += "1";
      }
      output += "2";
      if(!dsu.same_set(bottom, right) && !dsu.same_set(top, right) && !dsu.same_set(left, right)){
        output += "3";
      }
      if(!dsu.same_set(bottom, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
        output += "4";
      }
    } else if (visitors[i].s.f == 3){
      if(!dsu.same_set(left, bottom) && !dsu.same_set(top, right) && !dsu.same_set(left, right)){
        output += "1";
      }
      if(!dsu.same_set(bottom, right) && !dsu.same_set(top, right) && !dsu.same_set(bottom, top)){
        output += "2";
      }
      output += "3";
      if(!dsu.same_set(top, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
        output += "4";
      }
    } else {
      if(!dsu.same_set(left, bottom) && !dsu.same_set(top, left) && !dsu.same_set(left, right)){
        output += "1";
      }
      if(!dsu.same_set(bottom, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
        output += "2";
      }
      if(!dsu.same_set(top, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
        output += "3";
      }
      output += "4";
    }

    ans[visitors[i].s.s] = output;
  }

  for(auto& a: ans){
    cout << a << '\n';
  }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |       if(edgesIndex == edges.size() || edges[edgesIndex].f > 2*visitors[i].f){
      |          ~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42