제출 #394136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394136		maksim1744	이상적인 도시 (IOI12_city)	C++17	100 / 100	210 ms	18768 KiB

city

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