Submission #316956

#	Time	Username	Problem	Language	Result	Execution time	Memory
316956		AlexLuchianov	Countries (BOI06_countries)	C++14	100 / 100	62 ms	512 KiB

countries

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 1000;

struct Point{
  int x;
  int y;
  int s;
} v[1 + nmax];

struct Number{
  int x;
  int y;
  Number(int x_ = 0, int y_ = 1) {
    int d = std::__gcd(x_, y_);

    x = x_ / d;
    y = y_ / d;
  }
  bool operator < (Number a) {
    return 1LL * x * a.y < 1LL * a.x * y;
  }
  bool operator == (Number a) {
    return 1LL * x * a.y == 1LL * a.x * y;
  }
};

int dist(Point a, Point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

Number exert(Point a, Point b) {
  return {a.s, dist(a, b)};
}

int leader[1 + nmax], _count[1 + nmax];
Number emass[1 + nmax];

int dfs(int node) {
  if(leader[node] != node)
    leader[node] = dfs(leader[node]);
  return leader[node];
}

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

  int n;
  std::cin >> n;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i].x >> v[i].y >> v[i].s;
  
  for(int i = 1;i <= n; i++)
    for(int j = 1;j <= n; j++)
      if(i != j) {
        Number newmass = exert(v[i], v[j]);
        if(emass[j] < newmass) {
          emass[j] = newmass;
          leader[j] = i;
          _count[j] = 1;
        } else if(emass[j] == newmass)
          _count[j]++;
      }
  
  for(int i = 1;i <= n; i++)
    if(emass[i] < Number(v[i].s, 1) || emass[i] == Number(v[i].s, 1) || 1 < _count[i])
      leader[i] = i;

  for(int i = 1;i <= n; i++)
    if(emass[i] < Number(v[i].s, 1) || emass[i] == Number(v[i].s, 1))
      std::cout << "K\n";
    else if(_count[i] == 1)
      std::cout << dfs(i) << '\n';
    else
      std::cout << "D\n";
  return 0;
}

• Subtask 1: 100 / 100