Submission #483291

#TimeUsernameProblemLanguageResultExecution timeMemory
483291ivan_tudorIdeal city (IOI12_city)C++14
100 / 100
79 ms14456 KiB
#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++){
      |                  ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...