oj.uz

Submission #483291

# Submission time Handle Problem Language Result Execution time Memory
483291 2021-10-28T14:24:18 Z ivan_tudor Ideal city (IOI12_city) C++14
100 / 100
 79 ms 14456 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 2 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 2 ms 4940 KB Output is correct
7 Correct 2 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 2 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 2 ms 4940 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 3 ms 5044 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5848 KB Output is correct
2 Correct 12 ms 5912 KB Output is correct
3 Correct 31 ms 7092 KB Output is correct
4 Correct 30 ms 7108 KB Output is correct
5 Correct 68 ms 9032 KB Output is correct
6 Correct 58 ms 9108 KB Output is correct
7 Correct 58 ms 9376 KB Output is correct
8 Correct 58 ms 8908 KB Output is correct
9 Correct 58 ms 9412 KB Output is correct
10 Correct 58 ms 14456 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6632 KB Output is correct
2 Correct 15 ms 6392 KB Output is correct
3 Correct 39 ms 8984 KB Output is correct
4 Correct 36 ms 8264 KB Output is correct
5 Correct 78 ms 12864 KB Output is correct
6 Correct 67 ms 10604 KB Output is correct
7 Correct 79 ms 13068 KB Output is correct
8 Correct 68 ms 10684 KB Output is correct
9 Correct 64 ms 10188 KB Output is correct
10 Correct 65 ms 10052 KB Output is correct