oj.uz

답안 #480350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480350 2021-10-15T17:57:56 Z blue 이상적인 도시 (IOI12_city) C++17
100 / 100
 349 ms 61632 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
using namespace std;

int N;
vector<int> X, Y;

const int MX = 100'000;
const int INF = 1'000'000'000;


struct point
{
    int x;
    int y;
    int i;
    int rightNodes;
    int downNodes;
};


bool operator < (point A, point B)
{
    if(A.x != B.x) return A.x < B.x;
    return A.y < B.y;
}

set<point> P;

int getIndex(int x, int y)
{
    set<point>::iterator f = P.find(point{x, y, -1, -1, -1});
    if(f == P.end()) return -1;
    else return f->i;
}

long long new_ans = 0;





vector<int> up_edge[1+MX];
vector<int> down_edge[1+MX];
vector<int> Y_index_size(1+MX);
vector<int> Y_index_coord(1+MX);
int Y_max_index;

vector<int> Y_parent(1+MX);
vector<int> Y_subtree_sum(1+MX);

vector<int> point_Y_line(1+MX);

void Y_dfs(int u, int p)
{
    // cerr << "Y dfs " << u << ' ' << p << '\n';
    Y_subtree_sum[u] = Y_index_size[u];
    for(int v: up_edge[u])
    {
        if(v == p) continue;
        Y_parent[v] =  u;
        Y_dfs(v, u);
        Y_subtree_sum[u] += Y_subtree_sum[v];
    }
    for(int v: down_edge[u])
    {
        if(v == p) continue;
        Y_parent[v] =  u;
        Y_dfs(v, u);
        Y_subtree_sum[u] += Y_subtree_sum[v];
    }
}


vector<int> left_edge[1+MX];
vector<int> right_edge[1+MX];
vector<int> X_index_size(1+MX);
vector<int> X_index_coord(1+MX);
int X_max_index;

vector<int> X_parent(1+MX);
vector<int> X_subtree_sum(1+MX);

vector<int> point_X_line(1+MX);

void X_dfs(int u, int p)
{
    X_subtree_sum[u] = X_index_size[u];
    for(int v: left_edge[u])
    {
        if(v == p) continue;
        X_parent[v] =  u;
        X_dfs(v, u);
        X_subtree_sum[u] += X_subtree_sum[v];
    }
    for(int v: right_edge[u])
    {
        if(v == p) continue;
        X_parent[v] =  u;
        X_dfs(v, u);
        X_subtree_sum[u] += X_subtree_sum[v];
    }
}

long long init_dist = 0;

vector<int> dx{0, 0, +1, -1};
vector<int> dy{+1, -1, 0, 0};

long long final_ans = 0;

vector<bool> visit(MX, 0);


map<pair<int, int>, long long> X_delta, Y_delta; //adjust value when going from u to v.


void dfs(int u)
{
    for(int z = 0; z < 4; z++)
    {
        int v = getIndex(X[u] + dx[z], Y[u] + dy[z]);
        if(v == -1) continue;
        if(visit[v]) continue;

        visit[v] = 1;

        long long adjust_val;

        if(X[u] == X[v])
        {
            adjust_val = X_delta[ make_pair(point_X_line[u], point_X_line[v]) ];
        }
        else
        {
            // cerr << "! \n";
            // cerr << point_Y_line[u] << ' ' << point_Y_line[v] << ' ' << Y_delta[ make_pair(point_Y_line[u], point_Y_line[v]) ] <<'\n';
            adjust_val = Y_delta[ make_pair(point_Y_line[u], point_Y_line[v]) ];
        }

        init_dist += (N - adjust_val) - adjust_val;
        final_ans += init_dist;

        dfs(v);

        init_dist -= (N - adjust_val) - adjust_val;
    }
}


int DistanceSum(int N_, int *X_, int *Y_)
{
//PART 1: Normalize
    // cerr << "check\n";
    N = N_;
    X = vector<int>(N);
    Y = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        X[i] = X_[i];
        Y[i] = Y_[i];
    }

    int Xmin = X[0], Ymin = Y[0];
    for(int i = 1; i < N; i++)
    {
        Xmin = min(Xmin, X[i]);
        Ymin = min(Ymin, Y[i]);
    }


    for(int i = 0; i < N; i++)
    {
        X[i] = X[i] - Xmin + 1;
        Y[i] = Y[i] - Ymin + 1;      //CORRECT THIS!!!!!!

        // cerr << X[i] << ' ' << Y[i] << '\n';
    }

    for(int i = 0; i < N; i++)
    {
        P.insert(point{X[i], Y[i], i, -1, -1});
    }

    vector<int> Ylist[1+MX];
    for(int i = 0; i < N; i++)
    {
        Ylist[ X[i] ].push_back(Y[i]);
    }

    for(int x = 1; x <= MX; x++)
        sort(Ylist[x].begin(), Ylist[x].end());
    //
    //
    int curr_Y_index = 0;
    vector<int> Y_begin[1+MX], Y_end[1+MX];
    vector<int>* Y_index = new vector<int>[1+MX]; //FIGURE OUT WHY THIS WENT WRONG
    // vector<int> Y_index[1+MX];


    for(int x = 1; x <= MX; x++)
    {
        if(Ylist[x].empty()) continue;

        Y_begin[x].push_back(Ylist[x][0]);
        curr_Y_index++;
        Y_index[x].push_back(curr_Y_index);

        for(int i = 1; i < (int)Ylist[x].size(); i++)
        {
            if(Ylist[x][i-1] + 1 != Ylist[x][i])
            {
                Y_end[x].push_back(Ylist[x][i-1]);
                Y_begin[x].push_back(Ylist[x][i]);
                curr_Y_index++;
                Y_index[x].push_back(curr_Y_index);
            }
        }
        Y_end[x].push_back(Ylist[x].back());

        // cerr << "x = " << x << '\n';
        for(int v = 0; v < (int)Y_begin[x].size(); v++)
        {
            Y_index_size[ Y_index[x][v] ] = Y_end[x][v] - Y_begin[x][v] + 1;
            Y_index_coord[ Y_index[x][v] ] = x;

            for(int y = Y_begin[x][v]; y <= Y_end[x][v]; y++)
                point_Y_line[ getIndex(x, y) ] = Y_index[x][v];
        }
    }



    for(int x = 1; x+1 <= MX; x++)
    {
        if(Y_index[x].empty() || Y_index[x+1].empty()) continue;
        int q = 0;
        for(int p = 0; p < (int)Y_index[x].size(); p++)
        {
            if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q]))
            {
                down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]);
                up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]);
            }

            while(q+1 < (int)Y_begin[x+1].size() && Y_begin[x+1][q+1] <= Y_end[x][p])
            {
                q++;
                if(max(Y_begin[x][p], Y_begin[x+1][q]) <= min(Y_end[x][p], Y_end[x+1][q]))
                {
                    down_edge[Y_index[x][p]].push_back(Y_index[x+1][q]);
                    up_edge[Y_index[x+1][q]].push_back(Y_index[x][p]);
                }
            }
        }
    }
    Y_max_index = curr_Y_index;

    Y_parent[1] = 0;
    Y_dfs(1, 1);

    for(int u = 1; u <= Y_max_index; u++)
    {
        for(int v: down_edge[u])
        {
            if(v == Y_parent[u])
            {
                Y_delta[ make_pair(u, v) ] = (N - Y_subtree_sum[u]);
                Y_delta[ make_pair(v, u) ] = Y_subtree_sum[u];

                new_ans += (long long)Y_subtree_sum[u] * (long long)(N - Y_subtree_sum[u]);
            }
            else
            {
                Y_delta[ make_pair(u, v) ] = Y_subtree_sum[v];
                Y_delta[ make_pair(v, u) ] = (N - Y_subtree_sum[v]);

                new_ans += (long long)Y_subtree_sum[v] * (long long)(N - Y_subtree_sum[v]);

            }
        }
    }

    vector<int>* Xlist = new vector<int>[1+MX];
    for(int i = 0; i < N; i++)
    {
        Xlist[ Y[i] ].push_back(X[i]);
    }

    for(int y = 1; y <= MX; y++)
        sort(Xlist[y].begin(), Xlist[y].end());


    int curr_X_index = 0;
    vector<int>* X_begin = new vector<int>[1+MX];
    vector<int>* X_end = new vector<int>[1+MX];
    vector<int>* X_index = new vector<int>[1+MX]; //FIGURE OUT WHY THIS WENT WRONG



    for(int y = 1; y <= MX; y++)
    {
        if(Xlist[y].empty()) continue;

        X_begin[y].push_back(Xlist[y][0]);
        curr_X_index++;
        X_index[y].push_back(curr_X_index);

        for(int i = 1; i < (int)Xlist[y].size(); i++)
        {
            if(Xlist[y][i-1] + 1 != Xlist[y][i])
            {
                X_end[y].push_back(Xlist[y][i-1]);
                X_begin[y].push_back(Xlist[y][i]);
                curr_X_index++;
                X_index[y].push_back(curr_X_index);
            }
        }
        X_end[y].push_back(Xlist[y].back());

        for(int v = 0; v < (int)X_begin[y].size(); v++)
        {
            X_index_size[ X_index[y][v] ] = X_end[y][v] - X_begin[y][v] + 1;

            X_index_coord[ X_index[y][v] ] = y;

            for(int x = X_begin[y][v]; x <= X_end[y][v]; x++)
            {
                point_X_line[ getIndex(x, y) ] = X_index[y][v];
            }

        }
    }

    for(int y = 1; y+1 <= MX; y++)
    {
        if(X_index[y].empty() || X_index[y+1].empty()) continue;
        int q = 0;
        for(int p = 0; p < (int)X_index[y].size(); p++)
        {
            if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q]))
            {
                right_edge[X_index[y][p]].push_back(X_index[y+1][q]);
                left_edge[X_index[y+1][q]].push_back(X_index[y][p]);
            }

            while(q+1 < (int)X_begin[y+1].size() && X_begin[y+1][q+1] <= X_end[y][p])
            {
                q++;
                if(max(X_begin[y][p], X_begin[y+1][q]) <= min(X_end[y][p], X_end[y+1][q]))
                {
                    right_edge[X_index[y][p]].push_back(X_index[y+1][q]);
                    left_edge[X_index[y+1][q]].push_back(X_index[y][p]);
                }
            }
        }
    }
    X_max_index = curr_X_index;

    X_parent[1] = 0;
    X_dfs(1, 1);

    for(int u = 1; u <= X_max_index; u++)
    {
        for(int v: right_edge[u])
        {
            if(v == X_parent[u])
            {
                X_delta[ make_pair(u, v) ] = N - X_subtree_sum[u];
                X_delta[ make_pair(v, u) ] = N - (N - X_subtree_sum[u]);

                new_ans += (long long)X_subtree_sum[u] * (long long)(N - X_subtree_sum[u]);
            }
            else
            {
                X_delta[ make_pair(u, v) ] = X_subtree_sum[v];
                X_delta[ make_pair(v, u) ] = (N - X_subtree_sum[v]);

                new_ans += (long long)X_subtree_sum[v] * (long long)(N - X_subtree_sum[v]);
            }
        }
    }

    vector<int> dist0(N, INF);
    dist0[0] = 0;

    queue<int> tbv;
    tbv.push(0);

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();

        for(int z = 0; z < 4; z++)
        {
            int v = getIndex(X[u] + dx[z], Y[u] + dy[z]);
            if(v == -1) continue;

            if(dist0[v] <= dist0[u] + 1) continue;

            dist0[v] = dist0[u] + 1;
            tbv.push(v);
        }
    }

    for(int i = 0; i < N; i++)
    {
        init_dist += dist0[i];
    }


    final_ans = init_dist;

    visit[0] = 1;
    dfs(0);

    final_ans = final_ans/2;
    return int(new_ans % 1'000'000'000LL);
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 32348 KB Output is correct
2 Correct 22 ms 32328 KB Output is correct
3 Correct 22 ms 32324 KB Output is correct
4 Correct 24 ms 32332 KB Output is correct
5 Correct 22 ms 32336 KB Output is correct
6 Correct 22 ms 32396 KB Output is correct
7 Correct 23 ms 32388 KB Output is correct
8 Correct 22 ms 32460 KB Output is correct
9 Correct 23 ms 32464 KB Output is correct
10 Correct 23 ms 32460 KB Output is correct
11 Correct 24 ms 32392 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 32656 KB Output is correct
2 Correct 25 ms 32652 KB Output is correct
3 Correct 26 ms 32832 KB Output is correct
4 Correct 23 ms 32740 KB Output is correct
5 Correct 25 ms 32916 KB Output is correct
6 Correct 25 ms 32804 KB Output is correct
7 Correct 26 ms 32936 KB Output is correct
8 Correct 27 ms 32784 KB Output is correct
9 Correct 26 ms 32708 KB Output is correct
10 Correct 25 ms 32696 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 36548 KB Output is correct
2 Correct 55 ms 36588 KB Output is correct
3 Correct 115 ms 41408 KB Output is correct
4 Correct 113 ms 41124 KB Output is correct
5 Correct 244 ms 50296 KB Output is correct
6 Correct 249 ms 49732 KB Output is correct
7 Correct 240 ms 51012 KB Output is correct
8 Correct 243 ms 51160 KB Output is correct
9 Correct 237 ms 52420 KB Output is correct
10 Correct 269 ms 61632 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 37776 KB Output is correct
2 Correct 64 ms 37060 KB Output is correct
3 Correct 156 ms 45560 KB Output is correct
4 Correct 135 ms 43248 KB Output is correct
5 Correct 329 ms 58436 KB Output is correct
6 Correct 271 ms 51188 KB Output is correct
7 Correct 349 ms 59040 KB Output is correct
8 Correct 288 ms 50496 KB Output is correct
9 Correct 300 ms 48220 KB Output is correct
10 Correct 261 ms 47796 KB Output is correct