Submission #116242

#	Time	Username	Problem	Language	Result	Execution time	Memory
116242		nvmdava	Ideal city (IOI12_city)	C++17	55 / 100	285 ms	32632 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000000

long long res = 0;

set<pair<int, int> > loc[2];
int t[2];
int sz[2][100005];
int re[2];
vector<int> adj[2][100005];
int st;
int n;

int dfs(int x, int y){
   int id = ++re[1];
   int q = y++;
   set<pair<int, int> >::iterator it;
   while((it = loc[st].find({x, ++q})) != loc[st].end())
      loc[st].erase(it), sz[st][id]++;

   while((it = loc[st].find({x, --y})) != loc[st].end())
      loc[st].erase(it), sz[st][id]++;
   for(y++; y < q; y++){
      if(loc[st].count({x + 1, y})){
         int w = dfs(x + 1, y);
         adj[st][id].push_back(w);
         sz[st][id] += sz[st][w];
      }
      if(loc[st].count({x - 1, y})){
         int w = dfs(x - 1, y);
         sz[st][id] += sz[st][w];
         adj[st][id].push_back(dfs(x - 1, y));
      }
   }
   res += 1LL * (n - sz[st][id]) * sz[st][id];
   return id;
}

void solve(){
   dfs(t[st], t[st ^ 1]);
   st ^= 1;
}

int DistanceSum(int N, int *X, int *Y) {
   n = N;
   for(int i = 0; i < N; i++){
      X[i] -= 26543;
      Y[i] -= 51844;
      loc[0].insert({X[i], Y[i]});
      loc[1].insert({Y[i], X[i]});
   }
   t[0] = X[0];
   t[1] = Y[0];
   solve();
   solve();

   return res % MOD;
}

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