Submission #483291

#	Time	Username	Problem	Language	Result	Execution time	Memory
483291		ivan_tudor	Ideal city (IOI12_city)	C++14	100 / 100	79 ms	14456 KiB

city

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9;
struct nhelp{
  int x;
};
const int N = 1e5 + 5;
set<int> gr[N];
int sz[N];
void dfs(int nod, int dad, long long &ans, int tot){
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    dfs(x, nod, ans, tot);
    sz[nod] += sz[x];
  }
  ans += 1LL * sz[nod] * (tot - sz[nod]) % MOD;
  ans %= MOD;
}
long long solve(vector<pair<pair<int, int>, int>> coord){
  sort(coord.begin(), coord.end());
  int n = coord.size();
  int nrnod = 0;
  for(int i = 0; i < n; i++){
    if(i == 0)
      coord[i].second = ++nrnod, sz[nrnod] = 1;
    else if(coord[i].first.first == coord[i - 1].first.first && coord[i].first.second == coord[i - 1].first.second + 1)
      coord[i].second = coord[i - 1].second, sz[coord[i - 1].second]++;
    else
      coord[i].second = ++nrnod, sz[nrnod] = 1;
  }
  for(int i = 0; i < n; i++){
    swap(coord[i].first.first, coord[i].first.second);
  }
  sort(coord.begin(), coord.end());
  for(int i = 0; i < n; i++){
    if(i > 0 && coord[i].first.first == coord[i - 1].first.first && coord[i].first.second == coord[i - 1].first.second + 1){
      int a = coord[i].second, b = coord[i - 1].second;
      gr[a].insert(b);
      gr[b].insert(a);
    }
  }
  long long ans = 0;
  dfs(1, 0, ans, n);
  for(int i =1 ; i<=nrnod; i++){
    gr[i].clear();
    sz[i] = 0;
  }
  return ans;
}
int DistanceSum(int N, int *X, int *Y) {
  vector<pair<pair<int, int>, int>> coord(N);
  for(int i = 0; i < N; i++){
    coord[i] = {{X[i], Y[i]}, 0};
  }
  int ans1 = solve(coord);
  for(int i = 0; i < coord.size(); i++){
    swap(coord[i].first.first, coord[i].first.second);
    coord[i].second = 0;
  }
  int ans2 = solve(coord);
  return (1LL * ans1 + ans2) % MOD;

}

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i = 0; i < coord.size(); i++){
      |                  ~~^~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45