Submission #1208930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208930		i_love_spring	Countries (BOI06_countries)	C++20	100 / 100	57 ms	16456 KiB

countries

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
struct DSU {
  vector<int>v;
  DSU(int n) : v(n + 1, -1){}
  int find(int x){
    int y = x;
    while (v[x] > 0) x = v[x];
    while (x != y) y = exchange(v[y],x);
    return x;
  }
  bool unite(int x,int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (v[x] > v[y]) swap(x,y);
    v[x] += v[y];
    v[y] = x;
    return true;
  }
};
ll dist(int x,int y,int x1,int y1) {
  return (1ll * (x - x1) * (x - x1)) +( 1ll * (y - y1) * (y - y1));
}
void solve() {  
  int n;
  cin >> n;
  vector<ar<int,3>>a(n);
  for (int i = 0; i < n;i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
  vector<int> ans(n,0),used(n,0);
  vector<vector<ar<ll,2>>> v(n);
  vector<vector<int>> adj(n);
  for (int i = 0; i < n;i++) {
    bool ok = 0;
    ll id = 0,lsd = 1e9;
    for (int j = 0; j < n;j++) {
      if (i == j)continue;
      ll d = dist(a[i][0],a[i][1],a[j][0],a[j][1]); 
      v[i].push_back({a[j][2] - a[i][2] * d,j});
      if (a[j][2] * lsd > a[id][2] * d) {
        ok = 0;
        id = j;
        lsd = d;
      }
      else if (a[j][2] * lsd == a[id][2] * d) {
        ok = 1;
      }
    }
    sort(v[i].rbegin(),v[i].rend());
    if (v[i].front()[0] <= 0) ans[i] = -2;
    else if (ok) ans[i] = -1;
    else {
      adj[id].push_back(i);
    }
  }
  function<void(int,int)> dfs = [&](int u,int p) {
    ans[u] = ans[p];
    used[u] = 1;
    for (int v : adj[u]) {
      if (v != p) dfs(v,u);
    }
  };
  for (int i= 0; i < n;i++) {
    if (ans[i] != 0 && used[i] == 0) {
     // cerr << i << " ";
      int tmp = ans[i];
      ans[i] = i;
      dfs(i,i);
      ans[i] = tmp;
    }
  }
  for (int i = 0; i < n;i++) {
    if (ans[i] == -2) cout <<"K\n";
    else if (ans[i] == -1) cout << "D\n";
    else cout << ans[i] + 1<< "\n";
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
 // cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 

• Subtask 1: 100 / 100