제출 #38119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38119		funcsr	이상적인 도시 (IOI12_city)	C++14	23 / 100	409 ms	33396 KiB

city

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include <queue>
#include <map>
#include <algorithm>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(xs) xs.begin(), xs.end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000000
using namespace std;
int DX[4] = {-1, 0, 1, 0};
int DY[4] = {0, -1, 0, 1};

typedef pair<int, int> P;
map<P, int> mp;
vector<int> G[100000];
int par[100000], ord[100000], low[100000], sz[100000];
int W[100000];
vector<P> bridges, els;

void dfs(int x, int p, int r) {
  par[x] = p;
  sz[x] = 1;
  ord[x] = low[x] = r;
  for (int t : G[x]) if (t != p) {
    if (ord[t] != -1) {
      if (ord[x] < ord[t]) els.pb(P(x, t));
      low[x] = min(low[x], ord[t]);
      continue;
    }
    dfs(t, x, r+1);
    sz[x] += sz[t];
    low[x] = min(low[x], low[t]);
    if (ord[x] < low[t]) bridges.pb(P(x, t));
    else els.pb(P(x, t));
  }
}

int U[100000], R[100000];
vector<int> G2[100000];
int find(int x) {
  if (U[x] == x) return x;
  return U[x] = find(U[x]);
}
void unite(int x, int y) {
  x = find(x), y = find(y);
  if (x == y) return;
  if (R[x] < R[y]) swap(x, y);
  U[y] = x;
  R[x] += R[y];
}

int count(vector<P> seq) {
  sort(all(seq));
  int all = 0, sum = 0, ret = 0, last = seq[0]._1;
  for (P p : seq) all += p._2;
  for (P p : seq) {
    if (last != p._1) {
      int times = (1LL*sum*(all-sum))%MOD;
      ret = (ret + 1LL*(p._1-last)*times) % MOD;
      last = p._1;
    }
    sum += p._2;
  }
  return ret;
}

int DistanceSum(int N, int *X, int *Y) {
  rep(i, N) mp[P(X[i], Y[i])] = i;
  rep(i, N) {
    rep(k, 2) {
      P np = P(X[i]+DX[k], Y[i]+DY[k]);
      if (mp.find(np) != mp.end()) {
        int t = mp[np];
        G[i].pb(t);
        G[t].pb(i);
      }
    }
  }
  rep(i, N) ord[i] = low[i] = -1;
  dfs(0, -1, 0);
  rep(i, N) W[i] = 1;
  int s = 0;
  for (P p : bridges) {
    int u = p._1, v = p._2;
    W[u] += sz[v];
    W[v] += N-sz[v];
    s = (s + 1LL*sz[v]*(N-sz[v])) % MOD;
  }
  rep(i, N) U[i] = i, R[i] = 1;
  for (P p : els) unite(p._1, p._2);
  rep(i, N) G2[find(i)].pb(i);
  rep(c, N) if (G2[c].size() > 1) {
    assert(G2[c].size() >= 4);
    vector<P> xs, ys;
    for (int x : G2[c]) {
      xs.pb(P(X[x], W[x]));
      ys.pb(P(Y[x], W[x]));
    }
    s = (s+count(xs)) % MOD;
    s = (s+count(ys)) % MOD;
  }
  return s;
}

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