Submission #484467

#	Time	Username	Problem	Language	Result	Execution time	Memory
484467		iulia13	Ideal city (IOI12_city)	C++14	100 / 100	219 ms	20288 KiB

city

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define x first
#define y second
const ll mod = 1e9;
const int N = 1e5 + 5;
pair <int, int> v[N];
ll n;
map <pair<int, int>, int> mp;
map <pair<int, int>, int> gr;
vector <int> g[N];
int a[N];
ll s;
ll sp[N];
void dfs(int nod, int dad = 0)
{
    sp[nod] = a[nod];
    for (auto son : g[nod])
    {
        if (son == dad)
            continue;
        dfs(son, nod);
        sp[nod] += sp[son];
    }
    s = (s + sp[nod] * (n - sp[nod]) % mod) % mod;
}
int solve()
{
    s = 0;
    sort(v, v + n);
    gr[{v[0].x, v[0].y}] = 1;
    a[1] = 1;
    int nrg = 1;
    for (int i = 0; i < n - 1; i++)
    {
        if (v[i].x == v[i + 1].x && v[i].y + 1 == v[i + 1].y)
        {
            gr[{v[i + 1].x, v[i + 1].y}] = nrg;
            a[nrg]++;
        }
        else
        {
            gr[{v[i + 1].x, v[i + 1].y}] = ++nrg;
            a[nrg]++;
        }
    }
    for (int i = 0; i < n; i++)
    {
        int gr1 = gr[{v[i].x, v[i].y}];
        int gr2 = gr[{v[i].x + 1, v[i].y}];
        if (gr2)
            mp[{min(gr1, gr2), max(gr1, gr2)}] = 1;
        gr2 = gr[{v[i].x - 1, v[i].y}];
        if (gr2)
            mp[{min(gr1, gr2), max(gr1, gr2)}] = 1;
    }
    for (auto mypr : mp)
    {
        g[mypr.first.first].push_back(mypr.first.second);
        g[mypr.first.second].push_back(mypr.first.first);
    }
    dfs(1);
    return s;
}
int DistanceSum(int N, int *X, int *Y)
{
    n = N;
    for (int i = 0; i < n; i++)
        v[i].x = X[i], v[i].y = Y[i];
    ll ans = solve();
    mp.clear();
    gr.clear();
    for (int i = 1; i <= n; i++)
        g[i].clear(), a[i] = 0;
    for(int i = 0; i < n; i++)
        swap(v[i].x, v[i].y);
    return (ans + solve()) % mod;
}
/*
int main()
{
    int N; cin >> N;
	int *X = new int[N], *Y = new int[N];
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
	}

	cout << DistanceSum(N, X, Y) << "\n";


    return 0;
}*/

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