Submission #140359

#	Time	Username	Problem	Language	Result	Execution time	Memory
140359		darkkcyan	Ideal city (IOI12_city)	C++14	0 / 100	36 ms	4732 KiB

city

#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }


int DistanceSum(int n, int *x, int *y) {
    map<pair<int, int>, int> points;
    rep(i, n) points[{x[i], y[i]}] = i;

    struct Dsu {
        vector<int> root;
        Dsu(int n_): root(n_) {
            rep(i, len(root)) root[i] = i;
        }

        int find_set(int u) { return u == root[u] ? u : root[u] = find_set(root[u]); }
        void join(int u, int v) {
            if (rand() & 1) swap(u, v);
            // clog << "join " << u << ' ' << v << endl;
            root[find_set(u)] = find_set(v);
        }
    };

    Dsu dsu(n);
    rep(i, n) {
        if (points.count({x[i] + 1, y[i]})) {
            dsu.join(points[{x[i] + 1, y[i]}], i);
        }
    }

    vector<set<int>> gr(n);
    rep(i, n) {
        auto f = points.find({x[i], y[i] + 1});
        if (f == points.end()) continue;
        int u = dsu.find_set(i);
        int v = dsu.find_set(f->yy);
        gr[u].insert(v);
        gr[v].insert(u);
    }

    vector<pair<int, int>> gr_range(n, {INT_MAX, INT_MIN});
    rep(i, n) {
        int r = dsu.find_set(i);
        gr_range[r].xx = min(gr_range[r].xx, x[i]);
        gr_range[r].yy = max(gr_range[r].yy, x[i]);
    }

    auto intersect = [](pair<int, int> const& range1, pair<int, int> const& range2) -> pair<int, int> {
        assert(range1.xx <= range2.yy);
        assert(range2.xx <= range1.yy);
        return {max(range1.xx, range2.xx), min(range1.yy, range2.yy)};
    };

    vector<vector<llong>> dp(n);
    vector<int> tree_size(n);

    llong minus_ans = 0;

    function<void(int, int)> dfs = [&](int u, int p) {
        int cnt = gr_range[u].yy - gr_range[u].xx + 1;
        tree_size[u] = cnt;
        dp[u].resize(cnt);

        rep(i, cnt) {
            dp[u][i] = 1ll * i * (i + 1) / 2  + 1ll * (cnt - 1 - i) * (cnt - i) / 2ll;
            minus_ans += 1ll * i * (i + 1) / 2;
        }

        vector<llong> diff1(cnt), diff1_r(cnt);
        vector<llong> diff2(cnt), diff2_r(cnt);

        for (auto v: gr[u]) {
            if (v == p) continue;
            dfs(v, u);

            tree_size[u] += tree_size[v];

            auto inter = intersect(gr_range[u], gr_range[v]);
            // clog << "dfs inter " << u << ' ' << p << ":" << inter.xx << ' ' << inter.yy << endl;

            for (int i = inter.xx; i <= inter.yy; ++i) {
                int ux = i - gr_range[u].xx, vx = i - gr_range[v].xx;
                dp[u][ux] += dp[v][vx] + tree_size[v];
            }
            
            int t;
            t = inter.xx - gr_range[u].xx - 1;
            if (t >= 0) {
                diff1_r[t] += dp[v][inter.xx - gr_range[v].xx] + tree_size[v];
                diff2_r[t] += tree_size[v];
            }

            t = inter.yy - gr_range[u].xx + 1;
            if (t < cnt) {
                diff1[t] += dp[v][inter.yy - gr_range[v].xx] + tree_size[v];
                diff2[t] += tree_size[v];
            }
        }
        // clog << "dfs " << u << ' ' << p << endl;
        // rep(i, cnt) clog << diff1[i] << ' '; clog << endl;
        // rep(i, cnt) clog << diff2[i] << ' '; clog << endl;
        // rep(i, cnt) clog << diff1_r[i] << ' '; clog << endl;
        // rep(i, cnt) clog << diff2_r[i] << ' '; clog << endl;

        rep(i, cnt - 1) {
            diff1[i + 1] += diff1[i];
            diff2[i + 1] += diff2[i];
        }

        for (int i = cnt - 1; i > 0; --i) {
            diff1_r[i - 1] += diff1_r[i];
            diff2_r[i - 1] += diff2_r[i];
        }

        rep(i, cnt - 1) diff2[i + 1] += diff2[i];
        for (int i = cnt - 1; i > 0; --i) diff2_r[i - 1] += diff2_r[i];

        rep(i, cnt) dp[u][i] += diff1[i] + diff2[i] + diff1_r[i] + diff2_r[i];
        
        // rep(i, cnt) clog << dp[u][i] << ' ';
        // clog << endl;
    };

    dfs(dsu.find_set(0), -1);
    llong ans = 0;
    for (auto& i: dp) for (auto f: i) ans += f;

    ans -= minus_ans;
    return (int)(ans % (1000 * 1000 * 1000));
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45