Submission #259214

#	Time	Username	Problem	Language	Result	Execution time	Memory
259214		SamAnd	이상적인 도시 (IOI12_city)	C++17	100 / 100	440 ms	16064 KiB

city

//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005, M = 1000000000;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};

ll ans;

int n;
int X[N], Y[N];
map<pair<int, int>, int> mp;

int k;
int c[N];

void dfs(int i)
{
    if (c[i])
        return;
    c[i] = k;
    if (mp.find(m_p(X[i], Y[i] + 1)) != mp.end())
        dfs(mp[m_p(X[i], Y[i] + 1)]);
    if (mp.find(m_p(X[i], Y[i] - 1)) != mp.end())
        dfs(mp[m_p(X[i], Y[i] - 1)]);
}

int q[N];
vector<int> g[N];

void dfs1(int x, int p)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs1(h, x);
        q[x] += q[h];
    }
    ans += (q[x] * 1LL * (n - q[x]));
}

void solv()
{
    k = 0;
    memset(c, 0, sizeof c);
    for (int i = 0; i < n; ++i)
        g[i].clear();
    memset(q, 0, sizeof q);

    for (int i = 0; i < n; ++i)
    {
        if (!c[i])
        {
            ++k;
            dfs(i);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        if (mp.find(m_p(X[i] + 1, Y[i])) != mp.end())
        {
            g[c[i]].push_back(c[mp[m_p(X[i] + 1, Y[i])]]);
            g[c[mp[m_p(X[i] + 1, Y[i])]]].push_back(c[i]);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        sort(all(g[i]));
        vector<int> v;
        for (int j = 0; j < sz(g[i]); ++j)
        {
            if (!j || g[i][j] != g[i][j - 1])
                v.push_back(g[i][j]);
        }
        g[i] = v;
    }

    for (int i = 0; i < n; ++i)
    {
        q[c[i]]++;
    }

    dfs1(1, 1);
}

int DistanceSum(int N, int *X_, int *Y_)
{
    n = N;
    for (int i = 0; i < n; ++i)
    {
        X[i] = X_[i];
        Y[i] = Y_[i];
    }

    int minx = X[0];
    int miny = Y[0];
    for (int i = 0; i < n; ++i)
    {
        minx = min(minx, X[i]);
        miny = min(miny, Y[i]);
    }

    for (int i = 0; i < n; ++i)
    {
        X[i] -= (minx - 1);
        Y[i] -= (miny - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        mp[m_p(X[i], Y[i])] = i;
    }

    solv();

    mp.clear();
    for (int i = 0; i < n; ++i)
    {
        swap(X[i], Y[i]);
        mp[m_p(X[i], Y[i])] = i;
    }

    solv();

    return (ans % M);
}

Compilation message (stderr)

city.cpp: In function 'void dfs1(int, int)':
city.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~

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