Submission #230534

#	Time	Username	Problem	Language	Result	Execution time	Memory
230534		quocnguyen1012	Ideal city (IOI12_city)	C++14	100 / 100	141 ms	16996 KiB

city

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5, mod = 1e9;

vector<int> adj[maxn];
int sz[maxn], id[maxn], N, n;
int ans;

void dfs(int u, int p = -1)
{
  for(int v : adj[u]) if(v != p){
    dfs(v, u);
    ans += 1ll * (N - sz[v]) * sz[v] % mod;
    ans %= mod;
    sz[u] += sz[v];
  }
}

void solve(int X[], int Y[])
{
  memset(id, 0, sizeof id); memset(sz, 0, sizeof sz);
  for(int i = 0; i < N; ++i)
    adj[i].clear();
  vector<ii> vec;
  for(int i = 0; i < N; ++i)
    vec.eb(X[i], Y[i]);
  sort(vec.begin(), vec.end());

  map<ii, int> ma;
  n = 0;
  for(int i = 0; i < N; ++i){
    ma[vec[i]] = i;
    if(i == 0 || vec[i - 1].fi != vec[i].fi || vec[i - 1].se + 1 != vec[i].se)
      id[i] = ++n;
    else
      id[i] = id[i - 1];
    ++sz[id[i]];
    if(ma.count(mp(vec[i].fi - 1, vec[i].se))){
      int v = id[ma[mp(vec[i].fi - 1, vec[i].se)]];
      adj[id[i]].eb(v); adj[v].eb(id[i]);
    }
  }
  for(int i = 1; i <= n; ++i){
    sort(adj[i].begin(), adj[i].end());
    adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
  }
  dfs(1);
}

int DistanceSum(int _n, int X[], int Y[])
{
  N = _n;
  solve(X, Y); solve(Y, X);
  return ans;
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int _N; cin >> _N;
  int X[_N], Y[_N];
  for(int i = 0; i < _N; ++i){
    cin >> X[i] >> Y[i];
  }
  cout << DistanceSum(_N, X, Y);
}
#endif

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