Submission #417406

#	Time	Username	Problem	Language	Result	Execution time	Memory
417406		Collypso	Ideal city (IOI12_city)	C++17	100 / 100	294 ms	28400 KiB

city

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

const int MOD = 1e9;

using namespace std;

vt<vt<int>> tree;

map<pii, int> vertix;
int cur_vertix;

void dfs1(pii v, int cur)
{
    vertix[v] = cur;
    int u2 = vertix[{v.F, v.S + 1}];
    if (u2 == 1) dfs1({v.F, v.S + 1}, cur);
    int u3 = vertix[{v.F, v.S - 1}];
    if (u3 == 1) dfs1({v.F, v.S - 1}, cur);
    int u1 = vertix[{v.F + 1, v.S}];
    if (u1 > 1) tree[cur].pb(u1), tree[u1].pb(cur);
    else if (u1 == 1)
    {
        cur_vertix++, tree[cur].pb(cur_vertix), tree[cur_vertix].pb(cur);
        dfs1({v.F + 1, v.S}, cur_vertix);
    }
}

vt<ll> vertix_val, subtree_sum, used1, used2;

void dfs2(int v)
{
    used1[v] = 1;
    subtree_sum[v] = vertix_val[v];
    for(int to : tree[v])
    {
        if (used1[to]) continue;
        dfs2(to);
        subtree_sum[v] += subtree_sum[to];
    }
}

void dfs3(int v, ll& ans)
{
    used2[v] = 1;
    for(int to : tree[v])
    {
        if (used2[to]) continue;
        ans = (ans + (subtree_sum[to] * (subtree_sum[2] - subtree_sum[to])) % MOD) % MOD;
        dfs3(to, ans);
    }
}

ll Calc(int N, vt<pii> sorted)
{
    vertix.clear(), tree.clear(), vertix_val.clear(), subtree_sum.clear();
    used1.clear(), used2.clear();
    sort(all(sorted));
    for(int i = 0; i < N; i++) vertix[sorted[i]] = 1;
    cur_vertix = 1, tree.resize(N);
    for(int i = 0; i < N; i++)
        if (vertix[sorted[i]] == 1)
            cur_vertix++, dfs1(sorted[i], cur_vertix);
    vertix_val.resize(cur_vertix + 1);
    for(auto& x : vertix) vertix_val[x.S]++;
    subtree_sum.resize(cur_vertix + 1);
    used1.resize(cur_vertix + 1), used2.resize(cur_vertix + 1);
    ll ans = 0;
    dfs2(2), dfs3(2, ans);
    return ans;
}

int DistanceSum(int N, int* X, int* Y)
{
    vt<pii> x, y;
    for(int i = 0; i < N; i++) x.pb({X[i], Y[i]}), y.pb({Y[i], X[i]});
    return (Calc(N, x) + Calc(N, y)) % MOD;
}

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