oj.uz

Submission #568195

# Submission time Handle Problem Language Result Execution time Memory
568195 2022-05-24T21:37:22 Z benjaminkleyn Ideal city (IOI12_city) C++17
100 / 100
 59 ms 6152 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 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 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 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 2 ms 324 KB Output is correct
5 Correct 1 ms 408 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 356 KB Output is correct
9 Correct 1 ms 464 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 824 KB Output is correct
2 Correct 9 ms 852 KB Output is correct
3 Correct 19 ms 1472 KB Output is correct
4 Correct 18 ms 1588 KB Output is correct
5 Correct 38 ms 2712 KB Output is correct
6 Correct 33 ms 2772 KB Output is correct
7 Correct 32 ms 3040 KB Output is correct
8 Correct 36 ms 2612 KB Output is correct
9 Correct 36 ms 2912 KB Output is correct
10 Correct 45 ms 6152 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1332 KB Output is correct
2 Correct 10 ms 1236 KB Output is correct
3 Correct 31 ms 3284 KB Output is correct
4 Correct 25 ms 2708 KB Output is correct
5 Correct 59 ms 5400 KB Output is correct
6 Correct 41 ms 3792 KB Output is correct
7 Correct 58 ms 5540 KB Output is correct
8 Correct 51 ms 3920 KB Output is correct
9 Correct 43 ms 3784 KB Output is correct
10 Correct 39 ms 3440 KB Output is correct