Submission #591711

#	Time	Username	Problem	Language	Result	Execution time	Memory
591711		cheissmart	Ideal city (IOI12_city)	C++14	100 / 100	991 ms	49468 KiB

city

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
#define SORT_UNIQUE(v) sort(ALL(v)), (v).resize(unique(ALL(v)) - (v).begin())

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, M = 1000000000;

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

struct DS {
    vi p, pp, when, any, sz;
    V<vi> pps;
    DS(int n) {
        p.resize(n), pp.resize(n), any.resize(n), when.resize(n, -1), sz.resize(n, 1);
        iota(ALL(p), 0), iota(ALL(pp), 0), iota(ALL(any), 0);
    }
    int find(int u) {
        return p[u] == u ? u : p[u] = find(p[u]);
    }
    void add(int u, int v, int t) {
        u = find(u), v = find(v);
        if(u == v) return;
        int nw = SZ(p);
        p.PB(nw), pp.PB(nw), when.PB(t), sz.PB(sz[u] + sz[v]), any.PB(any[u]);
        p[u] = p[v] = pp[u] = pp[v] = nw;
    }
    void build() {
        pps.PB(pp);
        for(int j = 1; j < 17; j++) {
            vi npp;
            for(int i = 0; i < SZ(pp); i++)
                npp.PB(pps.back()[pps.back()[i]]);
            pps.PB(npp);
        }
    }
    pi find_root(int u, int t) {
        for(int i = 16; i >= 0; i--) {
            if(when[pps[i][u]] <= t) {
                u = pps[i][u];
            }
        }
        return {any[u], sz[u]};
    }
};

void add(int& a, int b) {
    a += b;
    if(a >= M) a -= M;
}

int solve(int n, int* x, int *y) {
    int ans = 0;
    map<pi, int> mp;
    map<int, vi> ys;
    int mnx = INF, mxx = -INF;
    for(int i = 0; i < n; i++) {
        mp[{x[i], y[i]}] = i;
        ys[x[i]].PB(y[i]);
        mnx = min(mnx, x[i]);
        mxx = max(mxx, x[i]);
    }
    DS dsl(n), dsr(n);
    for(int i = mnx; i <= mxx; i++) {
        int t = i - mnx;
        for(int yy:ys[i]) {
            if(mp.count({i, yy - 1})) {
                int u = mp[{i, yy}], v = mp[{i, yy - 1}];
                dsl.add(u, v, t);
            }
            if(mp.count({i - 1, yy})) {
                int u = mp[{i, yy}], v = mp[{i - 1, yy}];
                dsl.add(u, v, t);
            }
        }
    }
    for(int i = mxx; i >= mnx; i--) {
        int t = mxx - i;
        for(int yy:ys[i]) {
            if(mp.count({i, yy + 1})) {
                int u = mp[{i, yy}], v = mp[{i, yy + 1}];
                dsr.add(u, v, t);
            }
            if(mp.count({i + 1, yy})) {
                int u = mp[{i, yy}], v = mp[{i + 1, yy}];
                dsr.add(u, v, t);
            }
        }
    }
    dsl.build();
    dsr.build();
    vi sz(n, 1);
    for(int i = mnx; i < mxx; i++) {
        vi nodes;
        V<pi> edges;
        for(int yy:ys[i]) {
            if(mp.count({i + 1, yy})) {
                auto[u, szu] = dsl.find_root(mp[{i, yy}], i - mnx); 
                auto[v, szv] = dsr.find_root(mp[{i + 1, yy}], mxx - (i + 1));
                sz[u] = szu;
                sz[v] = szv;
                nodes.PB(u), nodes.PB(v);
                edges.EB(u, v);
            }
        }
        SORT_UNIQUE(nodes), SORT_UNIQUE(edges);
        assert(SZ(edges) == SZ(nodes) - 1);
        V<vi> G(SZ(nodes));
        for(auto[u, v]:edges) {
            u = lower_bound(ALL(nodes), u) - nodes.begin();
            v = lower_bound(ALL(nodes), v) - nodes.begin();
            G[u].PB(v), G[v].PB(u);
        }
        function<int(int, int)> dfs = [&] (int u, int p) {
            int siz = sz[nodes[u]];
            for(int v:G[u]) if(v != p) {
                int tt = dfs(v, u);
                add(ans, 1LL * tt * (n - tt) % M);
                siz += tt;
            }
            return siz;
        };
        dfs(0, -1);
    }
    return ans;
}

int DistanceSum(int n, int *x, int *y) {
    return (solve(n, x, y) + solve(n, y, x)) % M;
}

Compilation message (stderr)

city.cpp: In function 'int solve(int, int*, int*)':
city.cpp:111:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |                 auto[u, szu] = dsl.find_root(mp[{i, yy}], i - mnx);
      |                     ^
city.cpp:112:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |                 auto[v, szv] = dsr.find_root(mp[{i + 1, yy}], mxx - (i + 1));
      |                     ^
city.cpp:122:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |         for(auto[u, v]:edges) {
      |                 ^

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