oj.uz

Submission #38120

# Submission time Handle Problem Language Result Execution time Memory
38120 2018-01-01T11:55:22 Z funcsr Ideal city (IOI12_city) C++14
23 / 100
 406 ms 33396 KB 
#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) {
  int mx = *min_element(X, X+N),
      my = *min_element(Y, Y+N);
  rep(i, N) X[i] -= mx;
  rep(i, N) Y[i] -= my;
  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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9584 KB Output is correct
2 Correct 0 ms 9584 KB Output is correct
3 Correct 3 ms 9584 KB Output is correct
4 Correct 0 ms 9584 KB Output is correct
5 Incorrect 0 ms 9584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 13924 KB Output is correct
2 Correct 49 ms 14112 KB Output is correct
3 Correct 173 ms 19172 KB Output is correct
4 Correct 143 ms 19784 KB Output is correct
5 Correct 363 ms 30284 KB Output is correct
6 Correct 349 ms 29604 KB Output is correct
7 Correct 399 ms 28672 KB Output is correct
8 Correct 406 ms 29756 KB Output is correct
9 Correct 386 ms 30584 KB Output is correct
10 Correct 323 ms 33396 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 12288 KB Output isn't correct
2 Halted 0 ms 0 KB -