oj.uz

Submission #103349

# Submission time Handle Problem Language Result Execution time Memory
103349 2019-03-29T20:54:24 Z popovicirobert Ideal city (IOI12_city) C++14
55 / 100
 372 ms 29236 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);
            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 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 4 ms 768 KB Output is correct
5 Correct 6 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 5 ms 768 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4108 KB Output is correct
2 Correct 34 ms 4216 KB Output is correct
3 Correct 72 ms 9592 KB Output is correct
4 Correct 74 ms 9592 KB Output is correct
5 Correct 157 ms 18868 KB Output is correct
6 Correct 153 ms 18936 KB Output is correct
7 Correct 174 ms 19412 KB Output is correct
8 Correct 150 ms 18612 KB Output is correct
9 Correct 189 ms 19184 KB Output is correct
10 Correct 372 ms 28084 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6200 KB Output is correct
2 Correct 52 ms 5508 KB Output is correct
3 Correct 163 ms 14768 KB Output is correct
4 Correct 131 ms 12892 KB Output is correct
5 Correct 315 ms 28980 KB Output is correct
6 Correct 233 ms 22904 KB Output is correct
7 Correct 303 ms 29236 KB Output is correct
8 Correct 235 ms 23156 KB Output is correct
9 Incorrect 211 ms 21552 KB Output isn't correct
10 Halted 0 ms 0 KB -