Submission #568195

#	Time	Username	Problem	Language	Result	Execution time	Memory
568195		benjaminkleyn	Ideal city (IOI12_city)	C++17	100 / 100	59 ms	6152 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
pair<int,int> sq[100'000];

struct block
{
    int x, min_y, max_y;
    int sz() 
    {
        return max_y - min_y + 1;
    }
};

int m;
vector<block> blocks;
vector<vector<int>> neighbors;
vector<bool> vis;
ll res;

int dfs(int u)
{
    ll sz = blocks[u].sz();
    vis[u] = true;

    for (int v : neighbors[u])
        if (!vis[v])
            sz += dfs(v);

    res += sz * (n - sz) % 1'000'000'000;
    res %= 1'000'000'000;
    return sz;
}

void solve()
{
    sort(sq, sq + n);
    blocks.resize(0);
    int min_x = sq[0].first;
    int max_x = sq[n - 1].first;
    for (int i = 0; i < n; i++)
    {
        int min_y = sq[i].second;
        while (i < n && sq[i].first == sq[i + 1].first && sq[i].second + 1 == sq[i + 1].second)
            i++;
        
        blocks.push_back({sq[i].first, min_y, sq[i].second});
    }

    m = blocks.size();
    
    neighbors.assign(m, {});
    //int r = 1;
    for (int l = 0; l < m && sq[l].first < max_x; l++)
    {
        int r = l + 1;
        while (r < m && blocks[l].x == blocks[r].x) r++;

        for (; r < m && blocks[l].x + 1 == blocks[r].x; r++)
            if (!(blocks[r].max_y < blocks[l].min_y || blocks[l].max_y < blocks[r].min_y))
            {
                neighbors[r].push_back(l);
                neighbors[l].push_back(r);
            }
    }

    vis.assign(m, false);
    dfs(0);
}

int DistanceSum(int N, int *X, int *Y) 
{
    n = N;
    
    for (int i = 0; i < N; i++)
        sq[i].first = X[i], sq[i].second = Y[i];

    solve();

    for (int i = 0; i < N; i++)
        swap(sq[i].first, sq[i].second);

    solve();

    return (int) (res % 1'000'000'000);
}

/*
int nn;
int xx[100000], yy[100000];
int main()
{
    ifstream cin("example.txt");
    //ofstream fout("output.txt");
    cin >> nn;
    for (int i = 0; i < nn; i++)
        cin >> xx[i] >> yy[i];   
 
    fout << DistanceSum(nn, xx, yy) << '\n';
 
    return 0;
}
*/

Compilation message (stderr)

city.cpp: In function 'void solve()':
city.cpp:41:9: warning: unused variable 'min_x' [-Wunused-variable]
   41 |     int min_x = sq[0].first;
      |         ^~~~~

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