Submission #522091

#	Time	Username	Problem	Language	Result	Execution time	Memory
522091		cadmiumsky	Ideal city (IOI12_city)	C++14	100 / 100	225 ms	17148 KiB

city

#include <bits/stdc++.h>
#define ll long long
const int mod = 1e9;
using namespace std;
//g++ -std=c++17 -Wshadow -Wall -Wextra -o "%e" "%f" -g -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG
int n;
int nodes;

static ll solve(int *X, int *Y) {
  nodes = 0;
  map<int, set<int> > mat;
  map<int,int> w;
  map<int, map<int, int> > col;
  for(int i = 0; i < n; i++)
    col[X[i]][Y[i]];
  set<pair<int, int> > edg;
  vector<vector<int> > g;
  for(auto &v : col) {
    int x = v.first;
    for(auto &y : v.second) {
      if(col[x].find(y.first - 1) != col[x].end())
        y.second = col[x][y.first - 1], w[y.second]++;
      else
        w[nodes] = 1, y.second = nodes++;
      if(col.find(x - 1) == col.end() || col[x - 1].find(y.first) == col[x - 1].end()) 
        continue;
      //cerr << y.second<< ' '  <<  x << ' ' << y.first << ' ' << col[x - 1][y.first] << '\n';
      edg.insert({col[x - 1][y.first], col[x][y.first]});
    }
  }
  g.resize(nodes);
  for(auto x : edg) {
    //cerr << x.first << ' ' << x.second << '\n';
    g[x.first].push_back(x.second);
    g[x.second].push_back(x.first);
  }
  //cerr << "Ma-ta\n";
  ll total = 0;
  function<ll(int,int)> dfs = [&](int node, int f) {
    int sum = w[node];
    for(auto x : g[node])
      if(x != f)
        sum += dfs(x, node);
    //cerr << node << ' ' << f << ' ' << w[node] << '\n';
    total += (ll)(n - sum) * sum % mod;
    return sum;
  };
  dfs(0, 0);
  return total % mod;
}
int DistanceSum(int N, int *X, int *Y) {
  n = N;
  return (solve(X, Y) + solve(Y, X)) % mod;
}

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