oj.uz

Submission #573823

# Submission time Handle Problem Language Result Execution time Memory
573823 2022-06-07T09:08:52 Z kenjinemera Ideal city (IOI12_city) C++17
0 / 100
 37 ms 8124 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
            cout << "check\n";
            if ((nodes[i].miny <= nodes[point].maxy) || (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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 8124 KB Output isn't correct
2 Halted 0 ms 0 KB -