oj.uz

Submission #394136

# Submission time Handle Problem Language Result Execution time Memory
394136 2021-04-25T18:45:10 Z maksim1744 Ideal city (IOI12_city) C++17
100 / 100
 210 ms 18768 KB 
/*
    author:  Maksim1744
    created: 25.04.2021 21:32:49
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "C:/C++ libs/print.cpp"
#else
#define show(...) void(0)
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#endif

int DistanceSum(int n, int *X, int *Y) {
    vector<pair<int, int>> v;
    for (int i = 0; i < n; ++i) {
        v.eb(*X, *Y);
        ++X;
        ++Y;
    }
    show(v);
    ll ans = 0;
    for (int iii = 0; iii < 2; ++iii) {
        sort(v.begin(), v.end());
        set<pair<int, int>> sv(v.begin(), v.end());
        
        vector<vector<int>> g(n);
        int e = 0;
        set<pair<int, int>> hor;
        for (int i = 0; i < n; ++i) {
            auto [x, y] = v[i];
            if (sv.count({x, y + 1})) {
                int u = lowb(v, mp(x, y + 1));
                ++e;
                g[i].pb(u);
                g[u].pb(i);
            }
            if (sv.count({x + 1, y}) && (!sv.count({x, y + 1}) || !sv.count({x + 1, y + 1}))) {
                int u = lowb(v, mp(x + 1, y));
                ++e;
                g[i].pb(u);
                g[u].pb(i);
                hor.emplace(min(u, i), max(u, i));
            }
        }
        show(g);
        assert(e == n - 1);
        vector<bool> u(n, false);
        vector<int> sz(n);
        show(hor);
        function<void(int)> dfs = [&](int v) {
            u[v] = true;
            sz[v] = 1;
            for (int k : g[v]) {
                if (!u[k]) {
                    dfs(k);
                    sz[v] += sz[k];
                    if (hor.count({min(v, k), max(v, k)})) {
                        show(sz[k]);
                        ans += (ll)sz[k] * (n - sz[k]);
                    }
                }
            }
        };
        dfs(0);
        show(sz);
        show(ans);

        for (int i = 0; i < n; ++i) {
            swap(v[i].first, v[i].second);
        }
    }
    return ans % (int)1e9;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 4 ms 588 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2920 KB Output is correct
2 Correct 32 ms 3040 KB Output is correct
3 Correct 86 ms 6912 KB Output is correct
4 Correct 84 ms 6948 KB Output is correct
5 Correct 179 ms 13376 KB Output is correct
6 Correct 178 ms 13428 KB Output is correct
7 Correct 186 ms 13832 KB Output is correct
8 Correct 176 ms 13296 KB Output is correct
9 Correct 180 ms 13844 KB Output is correct
10 Correct 184 ms 18768 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3376 KB Output is correct
2 Correct 45 ms 3612 KB Output is correct
3 Correct 100 ms 7936 KB Output is correct
4 Correct 99 ms 7912 KB Output is correct
5 Correct 208 ms 15452 KB Output is correct
6 Correct 202 ms 14976 KB Output is correct
7 Correct 209 ms 15964 KB Output is correct
8 Correct 210 ms 14656 KB Output is correct
9 Correct 193 ms 13964 KB Output is correct
10 Correct 195 ms 13944 KB Output is correct