제출 #63391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63391		evpipis	이상적인 도시 (IOI12_city)	C++11	100 / 100	327 ms	22488 KiB

city

#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

컴파일 시 표준 에러 (stderr) 메시지

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45