oj.uz

Submission #13121

# Submission time Handle Problem Language Result Execution time Memory
13121 2015-01-31T10:28:42 Z gs14004 Ideal city (IOI12_city) C++14
100 / 100
 71 ms 23476 KB 
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int mod = 1e9;

vector<int> vx[100005],vy[100005];
vector<int> nx[100005],ny[100005];
vector<int> gx[100005],gy[100005];

int sx[100005], sy[100005];

int piv;

void const_graph(int n, vector<int> *v, vector<int> *c, vector<int> *g, int* s){
    piv = 0;
    for (int i=0; i<n; i++) {
        sort(v[i].begin(),v[i].end());
        c[i].resize(v[i].size());
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<v[i].size(); j++) {
            if(j && v[i][j-1] + 1 == v[i][j]){
                c[i][j] = c[i][j-1];
            }
            else c[i][j] = ++piv;
            s[c[i][j]]++;
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<v[i].size(); j++) {
            auto it = lower_bound(v[i+1].begin(),v[i+1].end(),v[i][j]);
            if(it != v[i+1].end() && *it == v[i][j]){
                int col = c[i+1][it - v[i+1].begin()];
                if(!g[c[i][j]].empty() && g[c[i][j]].back() == col){
                    continue;
                }
                else{
                    g[c[i][j]].push_back(col);
                    g[col].push_back(c[i][j]);
                }
            }
        }
    }
}

int *size;
vector<int> *graph;
int size2[100005];

int dfs(int x, int pa){
    int r = size[x];
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i] == pa) continue;
        r += dfs(graph[x][i],x);
    }
    size2[x] = r;
    return r;
}

long long solve(int n){
    memset(size2,0,sizeof(size2));
    dfs(1,0);
    long long ret = 0;
    for (int i=1; size[i]; i++) {
        for (int j=0; j<graph[i].size(); j++) {
            if(i > graph[i][j]) continue;
            int p = min(size2[i],size2[graph[i][j]]);
            ret += 1ll * (n-p) * p;
        }
    }
    return ret;
}

int DistanceSum(int N, int* X, int* Y){
    int minX = *min_element(X,X+N);
    int minY = *min_element(Y,Y+N);
    for (int i=0; i<N; i++) {
        X[i] -= minX;
        Y[i] -= minY;
    }
    for (int i=0; i<N; i++) {
        vx[X[i]].push_back(Y[i]);
    }
    const_graph(N,vx,nx,gx,sx);
    for (int i=0; i<N; i++) {
        vy[Y[i]].push_back(X[i]);
    }
    const_graph(N,vy,ny,gy,sy);
    long long ret = 0;
    size = sx, graph = gx;
    ret += solve(N);
    size = sy, graph = gy;
    ret += solve(N);
    return ret % mod;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17416 KB Output is correct
2 Correct 14 ms 17416 KB Output is correct
3 Correct 27 ms 18260 KB Output is correct
4 Correct 24 ms 18260 KB Output is correct
5 Correct 44 ms 19708 KB Output is correct
6 Correct 40 ms 19716 KB Output is correct
7 Correct 39 ms 19840 KB Output is correct
8 Correct 47 ms 19840 KB Output is correct
9 Correct 50 ms 19700 KB Output is correct
10 Correct 58 ms 23476 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17944 KB Output is correct
2 Correct 12 ms 17680 KB Output is correct
3 Correct 29 ms 19448 KB Output is correct
4 Correct 32 ms 19060 KB Output is correct
5 Correct 68 ms 22084 KB Output is correct
6 Correct 64 ms 20612 KB Output is correct
7 Correct 71 ms 22180 KB Output is correct
8 Correct 57 ms 20676 KB Output is correct
9 Correct 53 ms 20368 KB Output is correct
10 Correct 51 ms 20236 KB Output is correct