Submission #630929

#	Time	Username	Problem	Language	Result	Execution time	Memory
630929		sonamoo	Ideal city (IOI12_city)	C++14	100 / 100	219 ms	23876 KiB

city

#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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45