oj.uz

Submission #38117

# Submission time Handle Problem Language Result Execution time Memory
38117 2018-01-01T11:11:05 Z funcsr Ideal city (IOI12_city) C++14
23 / 100
 449 ms 33008 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];
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) {
      ret = (ret + 1LL*(p._1-last)*((1LL*sum*(all-sum)) % MOD)) % 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);
  int s = 0;
  for (P p : bridges) {
    int u = p._1, v = p._2;
    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) {
    vector<P> xs, ys;
    for (int x : G2[c]) if (G2[c].size() >= 2) {
      int w = 1;
      for (int t : G[x]) if (find(t) != c) {
        if (par[x] == t) w += N-sz[x];
        else w += sz[t];
      }
      xs.pb(P(X[x], w));
      ys.pb(P(Y[x], w));
    }
    s = (s+count(xs)) % MOD;
    s = (s+count(ys)) % MOD;
  }
  return s;
}

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:87:9: warning: unused variable 'u' [-Wunused-variable]
     int u = p._1, v = p._2;
         ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9196 KB Output is correct
2 Correct 0 ms 9196 KB Output is correct
3 Correct 0 ms 9196 KB Output is correct
4 Correct 0 ms 9196 KB Output is correct
5 Incorrect 0 ms 9196 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 9328 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 13532 KB Output is correct
2 Correct 66 ms 13732 KB Output is correct
3 Correct 153 ms 18784 KB Output is correct
4 Correct 183 ms 19396 KB Output is correct
5 Correct 439 ms 29888 KB Output is correct
6 Correct 449 ms 29212 KB Output is correct
7 Correct 446 ms 28288 KB Output is correct
8 Correct 429 ms 29372 KB Output is correct
9 Correct 409 ms 30200 KB Output is correct
10 Correct 353 ms 33008 KB Output is correct

Subtask #4
0 / 45.0

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