oj.uz

Submission #103350

# Submission time Handle Problem Language Result Execution time Memory
103350 2019-03-29T20:55:27 Z popovicirobert Ideal city (IOI12_city) C++14
100 / 100
 317 ms 28572 KB 
#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);
            mod(ans);
            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.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 896 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 6 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 768 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3972 KB Output is correct
2 Correct 35 ms 4100 KB Output is correct
3 Correct 69 ms 9180 KB Output is correct
4 Correct 70 ms 9240 KB Output is correct
5 Correct 161 ms 17968 KB Output is correct
6 Correct 160 ms 18196 KB Output is correct
7 Correct 170 ms 18552 KB Output is correct
8 Correct 135 ms 17948 KB Output is correct
9 Correct 176 ms 18480 KB Output is correct
10 Correct 316 ms 27192 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6020 KB Output is correct
2 Correct 40 ms 5252 KB Output is correct
3 Correct 151 ms 14228 KB Output is correct
4 Correct 118 ms 12404 KB Output is correct
5 Correct 311 ms 28140 KB Output is correct
6 Correct 220 ms 22156 KB Output is correct
7 Correct 317 ms 28572 KB Output is correct
8 Correct 232 ms 22392 KB Output is correct
9 Correct 212 ms 20784 KB Output is correct
10 Correct 196 ms 21340 KB Output is correct