Submission #304701

#	Time	Username	Problem	Language	Result	Execution time	Memory
304701		Hehehe	Ideal city (IOI12_city)	C++14	100 / 100	866 ms	32760 KiB

city

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
#define MOD 1000000000
using namespace std;

map <pair<int,int>,int> a;
set <int> L[DIM],L2[DIM];
deque <int> c;
pair <int,int> v[DIM];
int what_comp[DIM],Size[DIM],Size2[DIM],sum[DIM],sum2[DIM],viz[DIM];
int nr_nodes;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};

void dfs (int nod, int tata){

    sum[nod] = Size[nod];
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            sum[nod] += sum[vecin];
        }}

void dfs2 (int nod, int tata){

    sum2[nod] = Size2[nod];
    for (auto vecin : L2[nod])
        if (vecin != tata){
            dfs2 (vecin,nod);
            sum2[nod] += sum2[vecin];
        }}

int DistanceSum (int n, int *X, int *Y){
    int i;
    long long sol = 0;

    for (i=1;i<=n;i++){
        v[i] = make_pair (X[i-1],Y[i-1]);
        a[v[i]] = i;
    }


    int k = 0;
    //horizontal
    for(int i = 1; i <= n; i++){
        if(viz[i])continue;
        viz[i] = 1;

        what_comp[i] = ++k;

        int cnt = 0;

        int x = X[i - 1], y = Y[i - 1];
        while(a[{x, y + 1}]){
            y++;

            int idx = a[{x, y}];
            what_comp[idx] = k;
            viz[idx] = 1;

            cnt++;
        }

        y = Y[i - 1];
        while(a[{x, y - 1}]){
            y--;

            int idx = a[{x, y}];
            what_comp[idx] = k;
            viz[idx] = 1;

            cnt++;
        }

        Size[k] = ++cnt;
    }

    for(int i = 1; i <= n; i++){
        int I = X[i - 1], J = Y[i - 1];
        int now = what_comp[i];

        for(int l = 0; l < 4; l++){
            int x = I + di[l], y = J + dj[l];

            if(!a[{x, y}])continue;
            int next = what_comp[a[{x, y}]];

            if(now == next)continue;

            L[now].insert(next);
            L[next].insert(now);
        }
    }

    dfs(1, 0);

    for (i=1;i<=k;i++)
        sol += 1LL * sum[i] * (n - sum[i]);

    memset(viz, 0, sizeof(viz));
    memset(what_comp, 0, sizeof(what_comp));
    nr_nodes = 0;

    /// verticala

    for (i=1;i<=n;i++){
        if (!viz[i]){
            viz[i] = 1;
            what_comp[i] = ++nr_nodes;

            int x = v[i].first, y = v[i].second, cnt = 1;
            while (a[make_pair(x-1,y)]){
                x--, cnt++;
                int idx = a[make_pair(x,y)];
                viz[idx] = 1;
                what_comp[idx] = nr_nodes;
            }
            x = v[i].first;
            while (a[make_pair(x+1,y)]){
                x++, cnt++;
                int idx = a[make_pair(x,y)];
                viz[idx] = 1;
                what_comp[idx] = nr_nodes;
            }

            Size2[nr_nodes] = cnt;
        }
    }

    for (i=1;i<=n;i++){
        int ic = v[i].first, jc = v[i].second;
        int x = what_comp[i];
        for (int dir=0;dir<=3;dir++){
            int iv = ic + di[dir];
            int jv = jc + dj[dir];
            int idx = a[make_pair(iv,jv)];
            if (!idx)
                continue;
            int y = what_comp[idx];

            if (x != y){
                L2[x].insert(y);
                L2[y].insert(x);
            }}}




    dfs2 (1,0);

    for (i=1;i<=nr_nodes;i++)
        sol += 1LL * sum2[i] * (n - sum2[i]);

    return sol % MOD;

}

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