Submission #1213400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213400		sasde	Countries (BOI06_countries)	C++20	100 / 100	5 ms	328 KiB

countries

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
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<int>> adj(n);
  for (int i = 0; i < n;i++) {
    bool ok = 0;
    ll id = 0,lsd = 1e9,maxx=-1e18;
    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]); 
      // if(i==1)cout <<a[j][2]*lsd<<" "<<*d<<'\n';
      maxx=max(maxx,a[j][2] - a[i][2] * d);
      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;
      }
    }
    if (maxx<= 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]) {
       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();
  }
  return 0;
} 

• Subtask 1: 100 / 100