제출 #116245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116245		nvmdava	이상적인 도시 (IOI12_city)	C++17	100 / 100	282 ms	17968 KiB

city

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

long long res = 0;

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

int dfs(int x, int y){
   int id = ++re[st], 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++){
      for(int j = -1; j <= 1; j += 2){
         if(loc[st].count({x + j, y})){
            int w = dfs(x + j, y);
            adj[st][id].push_back(w);
            sz[st][id] += sz[st][w];
         }
      }

   }
   res += (n - sz[st][id]) * sz[st][id];
   return id;
}

int DistanceSum(int N, int *X, int *Y) {
   n = N;
   for(int i = 0; i < N; i++){
      X[i] -= 9;
      Y[i] -= 9;
      loc[0].insert({X[i], Y[i]});
      loc[1].insert({Y[i], X[i]});
   }
   t[0] = X[0];
   t[1] = Y[0];
   dfs(t[0], t[1]);
   st ^= 1;
   dfs(t[1], t[0]);
   return res % 1000000000;
}

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