oj.uz

Submission #630929

# Submission time Handle Problem Language Result Execution time Memory
630929 2022-08-17T10:47:48 Z sonamoo Ideal city (IOI12_city) C++14
100 / 100
 219 ms 23876 KB 
#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int,int>
#define mod 1000000000
#define SIZE 100005
#define ll long long int

using namespace std;

int n;
vector<pii> cell;
int sz[SIZE];
set<int> graph[SIZE];
map<pii , int> mp;
ll ans;

int dx[4] = {1 , 0 , -1 , 0};
int dy[4] = {0 , 1 , 0 , -1};

void init() {
    memset(sz , 0 , sizeof(sz));
    for (int i = 0; i < SIZE; i++) graph[i].clear();
    mp.clear();
}

void solve(int here , int pr) {
    for (auto there : graph[here]) {
        if (there == pr) continue;
        solve(there , here);
        sz[here] += sz[there];
    }

    ans += (ll)sz[here]*(ll)(n-sz[here]);
    ans %= mod;
}

void make_graph() {
    sort(cell.begin() , cell.end());

    int cnt = 1;
    mp[cell[0]] = cnt;
    sz[cnt]++;
    for (int i = 1; i < cell.size(); i++) {
        if (cell[i-1].first == cell[i].first && cell[i].second-cell[i-1].second == 1) {
            mp[cell[i]] = cnt;
        }
        else mp[cell[i]] = ++cnt;
        sz[cnt]++;
    }

    for (auto t : cell) {
        int x = t.first;
        int y = t.second;
        int idx = mp[t];

        for (int i = 0; i < 4; i++) {
            int xx = x+dx[i];
            int yy = y+dy[i];
            int idx2 = mp[{xx , yy}];

            if (idx2 != 0 && idx2 != idx) {
                graph[idx].insert(idx2);
            }
        }
    }
}

int DistanceSum(int N , int *X , int *Y) {
    n = N;
    for (int i = 0; i < n; i++) cell.push_back({X[i] , Y[i]});
    make_graph();
    solve(1 , -1);

    ans %= mod;

    init();
    for (int i = 0; i < cell.size(); i++) swap(cell[i].first , cell[i].second);
    make_graph();
    solve(1 , -1);

    ans %= mod;

    return ans;
}

Compilation message

city.cpp: In function 'void make_graph()':
city.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < cell.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < cell.size(); i++) swap(cell[i].first , cell[i].second);
      |                     ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5396 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Correct 4 ms 5392 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 3 ms 5424 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5460 KB Output is correct
11 Correct 3 ms 5396 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5460 KB Output is correct
2 Correct 5 ms 5528 KB Output is correct
3 Correct 5 ms 5660 KB Output is correct
4 Correct 7 ms 5588 KB Output is correct
5 Correct 7 ms 5716 KB Output is correct
6 Correct 8 ms 5536 KB Output is correct
7 Correct 6 ms 5716 KB Output is correct
8 Correct 6 ms 5664 KB Output is correct
9 Correct 7 ms 5532 KB Output is correct
10 Correct 6 ms 5532 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7308 KB Output is correct
2 Correct 32 ms 7312 KB Output is correct
3 Correct 80 ms 9748 KB Output is correct
4 Correct 78 ms 9960 KB Output is correct
5 Correct 162 ms 13768 KB Output is correct
6 Correct 158 ms 14064 KB Output is correct
7 Correct 161 ms 14288 KB Output is correct
8 Correct 155 ms 13640 KB Output is correct
9 Correct 161 ms 14516 KB Output is correct
10 Correct 176 ms 22928 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9112 KB Output is correct
2 Correct 38 ms 8356 KB Output is correct
3 Correct 103 ms 14412 KB Output is correct
4 Correct 92 ms 12672 KB Output is correct
5 Correct 219 ms 23424 KB Output is correct
6 Correct 179 ms 17808 KB Output is correct
7 Correct 213 ms 23876 KB Output is correct
8 Correct 210 ms 18116 KB Output is correct
9 Correct 170 ms 16840 KB Output is correct
10 Correct 172 ms 16552 KB Output is correct