Submission #573826

#	Time	Username	Problem	Language	Result	Execution time	Memory
573826		kenjinemera	Ideal city (IOI12_city)	C++17	100 / 100	69 ms	6264 KiB

city

#include <bits/stdc++.h>

using namespace std;

#define pi pair<int, int>
#define ll long long
#define pb push_back
#define f first 
#define s second
const int MAXN = 1000010;
const int MOD = 1'000'000'000;
pi nd[MAXN];
vector<vector<int>> adj;
int n;
ll ans;

struct group
{
    int x, miny, maxy;
};

vector<group> nodes; vector<bool> vis; vector<vector<int>> neighbours;

int dfs(int cur)
{
    ll weight = nodes[cur].maxy - nodes[cur].miny + 1;

    vis[cur] = 1;

    for (int child : adj[cur])
    {
        if (!vis[child]) weight += dfs(child);
    }
    
    ans += weight * (n - weight) % MOD;
    ans %= MOD;
    return weight;
}

void solve(int n)
{
    sort(nd, nd + n);
    nodes.resize(0); // don't forget to clear your container silly...

    // START GENERATING BLOCKS
    int i;

    for (i = 0; i < n; i++)
    {
        int miny = nd[i].s;

        while (i < n && nd[i].f == nd[i+1].f && nd[i].s + 1 == nd[i+1].s) i++;

        nodes.pb({nd[i].f, miny, nd[i].s});
    }

    int sz = nodes.size();

    int maxx = nd[n-1].f;

    adj.assign(sz, {});
    for (i = 0; i < sz && nodes[i].x < maxx; i++)
    {
        int point = i + 1;

        while (point < sz && nodes[i].x == nodes[point].x) point++;

        while (point < sz && nodes[i].x + 1 == nodes[point].x)
        {   
            // find overlapping y ranges
            if (!(nodes[point].maxy < nodes[i].miny || nodes[i].maxy < nodes[point].miny))
            {
                adj[i].pb(point);
                adj[point].pb(i);
            }
            point++;
        }
    }


    // perform the bloody DFS
    vis.assign(sz, 0);
    dfs(0);
}

int DistanceSum(int N, int *X, int *Y)
{
    n = N; // damn DFS
    
    // HORIZONTAL TREE
    for (int i = 0; i < N; i++)
    {
        nd[i] = {X[i], Y[i]};
    }

    solve(n);

    // VERTICAL TREE
    for (int i = 0; i < N; i++)
    {
        swap(nd[i].f, nd[i].s);
    }

    solve(n);

    // return our answer MOD
    return (int) (ans % MOD);
}

//int main()
//{
//    freopen("input.txt", "r", stdin);
//    
//    cin >> n;
//
//    int x[n], y[n];
//
//    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];  
//
//    cout << DistanceSum(n, x, y) << "\n";
//
//    return 0;
//}

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