oj.uz

Submission #63391

# Submission time Handle Problem Language Result Execution time Memory
63391 2018-08-01T16:11:06 Z evpipis Ideal city (IOI12_city) C++11
100 / 100
 327 ms 22488 KB 
#include <bits/stdc++.h>
using namespace std;

//#define TEST

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;

#ifdef TEST
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#endif // TEST

const int len = 1e5+5, mod = 1e9;
int par[len], dep[len], cnt[len], val[len], sum[len], n;
pair<ii, int> arr[len];
vector<int> adj[len];
set<ii> myset;

int add(int a, int b){
    return (a+b)%mod;
}

int sub(int a, int b){
    return (mod+a-b)%mod;
}

int mul(int a, int b){
    return (a*1LL*b)%mod;
}

int fin(int i){
    if (par[i] == i) return i;
    return par[i] = fin(par[i]);
}

void join(int i, int j){
    i = fin(i), j = fin(j);
    if (i != j)
        par[i] = j, val[j] += val[i];
}

bool comp(pair<ii, int> a, pair<ii, int> b){
    if (a.fi.se < b.fi.se) return true;
    if (a.fi.se > b.fi.se) return false;
    return (a.fi.fi < b.fi.fi);
}

int dfs(int u, int p){
    //printf("u = %d, p = %d, val = %d\n", u, p, val[u]);
    cnt[u] = val[u];
    sum[u] = mul(val[u], dep[u]);

    int ans = 0;
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        if (v == p) continue;

        dep[v] = dep[u]+1;
        ans = add(ans, dfs(v, u));
        cnt[u] = add(cnt[u], cnt[v]);
        sum[u] = add(sum[u], sum[v]);
    }

    //printf("u = %d, cnt = %d, sum = %d\n", u, cnt[u], sum[u]);
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        if (v == p) continue;

        ans = add(ans, mul(sub(cnt[u], cnt[v]), sub(sum[v], mul(cnt[v], dep[u]))));
        //ans += (cnt[u]-val[u]-cnt[v]+1) * (sum[v]-cnt[v]*1LL*dep[u]);
    }

    //printf("u = %d, ans = %d\n", u, ans);
    return ans;
}

int solve(){
    //printf("solve starts\n");
    myset.clear();
    for (int i = 0; i < n; i++){
        par[i] = i;
        val[i] = 1;
        cnt[i] = 0;
        adj[i].clear();
    }

    sort(arr, arr+n);
    for (int i = 0; i < n-1; i++)
        if (arr[i].fi.fi == arr[i+1].fi.fi && arr[i].fi.se+1 == arr[i+1].fi.se)
            join(arr[i].se, arr[i+1].se);

    sort(arr, arr+n, comp);
    for (int i = 0; i < n-1; i++){
        int a = fin(arr[i].se), b = fin(arr[i+1].se);
        if (arr[i].fi.se == arr[i+1].fi.se && arr[i].fi.fi+1 == arr[i+1].fi.fi && !myset.count(mp(a, b))){
            adj[a].pb(b);
            adj[b].pb(a);
            myset.insert(mp(a, b));
            myset.insert(mp(b, a));
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
        if (cnt[i] == 0 && adj[i].size())
            ans = add(ans, dfs(i, i));
    return ans;
}

int DistanceSum(int N, int *X, int *Y){
    n = N;
    for (int i = 0; i < n; i++)
        arr[i].fi = mp(X[i], Y[i]);
    for (int i = 0; i < n; i++)
        arr[i].se = i;

    int ans = solve();
    for (int i = 0; i < n; i++)
        swap(arr[i].fi.fi, arr[i].fi.se);
    ans = add(ans, solve());

    return ans;
}

#ifdef TEST
int main() {
  freopen("example.txt", "r", stdin);
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, i;
  tmp = scanf("%d", &N);
  assert(tmp == 1);
  int *sq_x, *sq_y;
  sq_x = (int*) malloc(N * sizeof(int));
  sq_y = (int*) malloc(N * sizeof(int));
  for (i = 0; i < N; i++) {
    tmp = scanf("%d %d", &sq_x[i], &sq_y[i]);
    assert(tmp == 2);
  }
  int ds = DistanceSum(N, sq_x, sq_y);
  printf("%d\n", ds);

  return 0;

}
#endif

Compilation message

city.cpp: In function 'int dfs(int, int)':
city.cpp:59:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
city.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2684 KB Output is correct
2 Correct 4 ms 2796 KB Output is correct
3 Correct 4 ms 2796 KB Output is correct
4 Correct 5 ms 2944 KB Output is correct
5 Correct 6 ms 3056 KB Output is correct
6 Correct 7 ms 3056 KB Output is correct
7 Correct 6 ms 3056 KB Output is correct
8 Correct 6 ms 3056 KB Output is correct
9 Correct 6 ms 3056 KB Output is correct
10 Correct 6 ms 3056 KB Output is correct
11 Correct 6 ms 3060 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3196 KB Output is correct
2 Correct 10 ms 3200 KB Output is correct
3 Correct 9 ms 3352 KB Output is correct
4 Correct 7 ms 3352 KB Output is correct
5 Correct 7 ms 3412 KB Output is correct
6 Correct 7 ms 3412 KB Output is correct
7 Correct 10 ms 3580 KB Output is correct
8 Correct 7 ms 3580 KB Output is correct
9 Correct 8 ms 3580 KB Output is correct
10 Correct 7 ms 3580 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4292 KB Output is correct
2 Correct 23 ms 4568 KB Output is correct
3 Correct 63 ms 6008 KB Output is correct
4 Correct 60 ms 6620 KB Output is correct
5 Correct 112 ms 9212 KB Output is correct
6 Correct 120 ms 10168 KB Output is correct
7 Correct 116 ms 11000 KB Output is correct
8 Correct 120 ms 11364 KB Output is correct
9 Correct 131 ms 12852 KB Output is correct
10 Correct 195 ms 18828 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18828 KB Output is correct
2 Correct 46 ms 18828 KB Output is correct
3 Correct 143 ms 18828 KB Output is correct
4 Correct 110 ms 18828 KB Output is correct
5 Correct 327 ms 20780 KB Output is correct
6 Correct 213 ms 20780 KB Output is correct
7 Correct 263 ms 22488 KB Output is correct
8 Correct 169 ms 22488 KB Output is correct
9 Correct 192 ms 22488 KB Output is correct
10 Correct 191 ms 22488 KB Output is correct