Submission #780833

#TimeUsernameProblemLanguageResultExecution timeMemory
780833NothingXDIdeal city (IOI12_city)C++17
100 / 100
507 ms15716 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef complex<ld> point; void debug_out(){cerr << endl;} template<typename H, typename... T> void debug_out(H h, T... t){ cerr << h << ' '; debug_out(t...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 1e5 + 10; const int inf = 2147483647; const int mod = 1e9; int add(int x, int y){ int res = x + y; if (res >= mod) return res - mod; if (res < 0) return res + mod; return res; } int n, ans, x[maxn], y[maxn], sz[maxn]; vector<int> valx[maxn], valy[maxn]; vector<int> g[maxn]; void dfs(int v, int p = -1){ //debug(v); for (auto u: g[v]){ if (u != p){ dfs(u, v); sz[v] += sz[u]; } } ans = add(ans, 1ll * sz[v] * (n-sz[v]) % mod); //debug(v, sz[v]); } int DistanceSum(int N, int *X, int *Y) { n = N; int mnx = inf, mny = inf, mx = 0, my = 0; for (int i = 1; i <= n; i++){ x[i] = X[i-1]; y[i] = Y[i-1]; mnx = min(mnx, x[i]); mny = min(mny, y[i]); } mnx--; mny--; for (int i = 1; i <= n; i++){ x[i] -= mnx; y[i] -= mny; valx[x[i]].push_back(y[i]); valy[y[i]].push_back(x[i]); mx = max(mx, x[i]); my = max(my, y[i]); cerr << x[i] << ' ' << y[i] << endl; } int cnt = 0; vector<pair<int,pii>> ver; for (int i = 1; i <= mx; i++){ vector<pair<int,pii>> tmp; sort(all(valx[i])); int l = valx[i][0]; for (int j = 1; j < valx[i].size(); j++){ if (valx[i][j] != valx[i][j-1] + 1){ cnt++; tmp.push_back({cnt, {l, valx[i][j-1]}}); //debug(i, cnt, l, valx[i][j-1]); sz[cnt] = valx[i][j-1] - l + 1; l = valx[i][j]; } } cnt++; tmp.push_back({cnt, {l, valx[i].back()}}); //debug(i, cnt, l, valx[i].back()); sz[cnt] = valx[i].back() - l + 1; int ptr = 0; for (auto [x, y]: tmp){ while(ptr < ver.size() && ver[ptr].S.S <= y.S){ if (y.F <= ver[ptr].S.S){ // debug(ver[ptr].F, x); g[ver[ptr].F].push_back(x); g[x].push_back(ver[ptr].F); } ptr++; } if (ptr != ver.size() && ver[ptr].S.F <= y.S){ // debug(ver[ptr].F, x); g[ver[ptr].F].push_back(x); g[x].push_back(ver[ptr].F); } } ver = tmp; } dfs(1); for (int i = 1; i <= cnt; i++){ g[i].clear(); } memset(sz, 0, sizeof sz); ver.clear(); cnt = 0; for (int i = 1; i <= my; i++){ vector<pair<int,pii>> tmp; sort(all(valy[i])); int l = valy[i][0]; for (int j = 1; j < valy[i].size(); j++){ if (valy[i][j] != valy[i][j-1] + 1){ cnt++; // debug(i, cnt, l, valy[i][j-1]); tmp.push_back({cnt, {l, valy[i][j-1]}}); sz[cnt] = valy[i][j-1] - l + 1; l = valy[i][j]; } } cnt++; tmp.push_back({cnt, {l, valy[i].back()}}); //debug(i, cnt, l, valy[i].back()); sz[cnt] = valy[i].back() - l + 1; int ptr = 0; for (auto [x, y]: tmp){ while(ptr < ver.size() && ver[ptr].S.S <= y.S){ if (y.F <= ver[ptr].S.S){ // debug(ver[ptr].F, x); g[ver[ptr].F].push_back(x); g[x].push_back(ver[ptr].F); } ptr++; } if (ptr != ver.size() && ver[ptr].S.F <= y.S){ // debug(ver[ptr].F, x); g[ver[ptr].F].push_back(x); g[x].push_back(ver[ptr].F); } } ver = tmp; } dfs(1); return ans; }

Compilation message (stderr)

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int j = 1; j < valx[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
city.cpp:94:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |    while(ptr < ver.size() && ver[ptr].S.S <= y.S){
      |          ~~~~^~~~~~~~~~~~
city.cpp:102:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    if (ptr != ver.size() && ver[ptr].S.F <= y.S){
      |        ~~~~^~~~~~~~~~~~~
city.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int j = 1; j < valy[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
city.cpp:137:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    while(ptr < ver.size() && ver[ptr].S.S <= y.S){
      |          ~~~~^~~~~~~~~~~~
city.cpp:145:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    if (ptr != ver.size() && ver[ptr].S.F <= y.S){
      |        ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...