Submission #1214768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214768		LIA	Ideal city (IOI12_city)	C++17	23 / 100	33 ms	8008 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll,ll,ll> plll;
typedef vector<plll> vplll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define loop(i,s,e) for(ll i=(s); i<(e); ++i)
#define loopr(i,e,s) for(ll i=(e)-1; i>=(s); --i)
#define all(a) a.begin(),a.end()
const ll inf =  1000000000;

vvll g1, g2;
vll w1, w2;
vll sub1, sub2;
ll total1 = 0, total2 = 0, n, ans = 0;

ll dfs1(ll u, ll p) {
    ll s = w1[u];
    for (ll v : g1[u]) {
        if (v != p) {
            s += dfs1(v, u);
        }
    }
    sub1[u] = s;
    if (p != -1) {
        ans = (ans + (s * (total1 - s)) % inf) % inf;
    }
    return s;
}

ll dfs2(ll u, ll p) {
    ll s = w2[u];
    for (ll v : g2[u]) {
        if (v != p) {
            s += dfs2(v, u);
        }
    }
    sub2[u] = s;
    if (p != -1) {
        ans = (ans + (s * (total2 - s)) % inf) % inf;
    }
    return s;
}

int DistanceSum(int nn, int *x, int *y) {
    ans = 0;
    n = nn;
    vll xs;
    vll ys;
    xs.reserve(n);
    ys.reserve(n);
    loop(i,0,n) {
        xs.push_back(x[i]);
        ys.push_back(y[i]);
    }
    sort(all(xs));
    xs.erase(unique(all(xs)), xs.end());
    sort(all(ys));
    ys.erase(unique(all(ys)), ys.end());
    ll m1 = xs.size();
    ll m2 = ys.size();
    g1.assign(m1, vll());
    g2.assign(m2, vll());
    vll xid(n);
    vll yid(n);
    loop(i,0,n) {
        xid[i] = lower_bound(all(xs), x[i]) - xs.begin();
        yid[i] = lower_bound(all(ys), y[i]) - ys.begin();
    }
    loop(i,0,m1-1) {
        g1[i].push_back(i+1);
        g1[i+1].push_back(i);
    }
    loop(i,0,m2-1) {
        g2[i].push_back(i+1);
        g2[i+1].push_back(i);
    }
    w1.assign(m1, 0);
    w2.assign(m2, 0);
    loop(i,0,n) {
        w1[xid[i]]++;
        w2[yid[i]]++;
    }
    total1 = 0;
    loop(i,0,m1) {
        total1 += w1[i];
    }
    sub1.assign(m1, 0);
    if (m1 > 0) {
        dfs1(0, -1);
    }
    total2 = 0;
    loop(i,0,m2) {
        total2 += w2[i];
    }
    sub2.assign(m2, 0);
    if (m2 > 0) {
        dfs2(0, -1);
    }
    return ans;
}

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