제출 #103349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103349		popovicirobert	이상적인 도시 (IOI12_city)	C++14	55 / 100	372 ms	29236 KiB

city

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> PII;
typedef vector <int> VI;
typedef vector <VI> VVI;

const int MOD = (int) 1e9;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

int dfs(int nod, int par, VVI &g, VI &w, VI &lvl, VI &sp) {
    lvl[nod] = lvl[par] + 1, sp[nod] = 0;
    int ans = 0;
    for(auto it : g[nod]) {
        if(lvl[it] == 0) {
            ans += dfs(it, nod, g, w, lvl, sp);
            sp[nod] += sp[it];
            mod(sp[nod]);
        }
    }
    ans = (ans + 2LL * w[nod] * sp[nod] * lvl[nod]) % MOD;
    for(auto it : g[nod]) {
        if(lvl[it] == lvl[nod] + 1) {
            ans = (ans + 1LL * (sp[nod] - sp[it] + MOD) * lvl[nod] * sp[it]) % MOD;
        }
    }
    sp[nod] += w[nod];
    mod(sp[nod]);
    return ans;
}

inline int solve(int N, int *X, int *Y, VVI &cx, VVI &cy, VI &nrm_x, VI &nrm_y) {
    map <PII, int> mp, vis;
    VVI g(N + 1);
    VI w(N + 1);
    int i, cur = 0;
    for(int x = 1; x <= N; x++) {
        sort(cx[x].begin(), cx[x].end());
        int sz = cx[x].size();
        i = 0;
        while(i < sz) {
            int j = i;
            cur++;
            while(j < sz && cx[x][i] + j - i == cx[x][j]) {
                auto it = mp[{nrm_x[x] - 1, cx[x][j]}];
                if(it != 0) {
                    if(vis[{it, cur}] == 0) {
                        g[cur].push_back(it);
                        g[it].push_back(cur);
                        vis[{it, cur}] = vis[{cur, it}] = 1;
                    }
                }
                it = mp[{nrm_x[x] + 1, cx[x][j]}];
                if(it != 0) {
                    if(vis[{it, cur}] == 0) {
                        g[cur].push_back(it);
                        g[it].push_back(cur);
                        vis[{it, cur}] = vis[{cur, it}] = 1;
                    }
                }
                w[cur]++;
                mp[{nrm_x[x], cx[x][j]}] = cur;
                j++;
            }
            i = j;
        }
    }
    VI lvl(N + 1), sp(N + 1);
    int aux = dfs(1, 0, g, w, lvl, sp);
    int ans = 0;
    for(i = 1; i <= cur; i++) {
        ans = (ans + 1LL * w[i] * lvl[i] * (N - w[i])) % MOD;
    }
    mod(aux);
    ans += MOD - aux;
    mod(ans);
    return ans;
}

int DistanceSum(int N, int *X, int *Y) {
    VVI cx(N + 1), cy(N + 1);
    VI nrm_x(N + 1), nrm_y(N + 1);
    map <int, int> mpx, mpy;
    int curx = 0, cury = 0;
    for(int i = 0; i < N; i++) {
        if(mpx[X[i]] == 0) {
            curx++;
            mpx[X[i]] = curx;
            nrm_x[curx] = X[i];
        }
        if(mpy[Y[i]] == 0) {
            cury++;
            mpy[Y[i]] = cury;
            nrm_y[cury] = Y[i];
        }
        cx[mpx[X[i]]].push_back(Y[i]);
        cy[mpy[Y[i]]].push_back(X[i]);
    }
    int ans = solve(N, X, Y, cx, cy, nrm_x, nrm_y);
    ans += solve(N, Y, X, cy, cx, nrm_y, nrm_x);
    mod(ans);
    return ans;
}

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