oj.uz

Submission #573826

# Submission time Handle Problem Language Result Execution time Memory
573826 2022-06-07T09:14:50 Z kenjinemera Ideal city (IOI12_city) C++17
100 / 100
 69 ms 6264 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 312 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 816 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Correct 20 ms 1488 KB Output is correct
4 Correct 18 ms 1496 KB Output is correct
5 Correct 39 ms 2748 KB Output is correct
6 Correct 35 ms 2776 KB Output is correct
7 Correct 34 ms 2964 KB Output is correct
8 Correct 35 ms 2652 KB Output is correct
9 Correct 33 ms 2896 KB Output is correct
10 Correct 40 ms 6264 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1356 KB Output is correct
2 Correct 9 ms 1204 KB Output is correct
3 Correct 28 ms 3340 KB Output is correct
4 Correct 21 ms 2680 KB Output is correct
5 Correct 59 ms 5444 KB Output is correct
6 Correct 39 ms 3816 KB Output is correct
7 Correct 69 ms 5516 KB Output is correct
8 Correct 48 ms 3920 KB Output is correct
9 Correct 38 ms 3792 KB Output is correct
10 Correct 40 ms 3420 KB Output is correct