oj.uz

Submission #484467

# Submission time Handle Problem Language Result Execution time Memory
484467 2021-11-03T15:13:08 Z iulia13 Ideal city (IOI12_city) C++14
100 / 100
 219 ms 20288 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2764 KB Output is correct
2 Correct 3 ms 2768 KB Output is correct
3 Correct 3 ms 2892 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 4 ms 2892 KB Output is correct
6 Correct 4 ms 2892 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct
9 Correct 4 ms 2892 KB Output is correct
10 Correct 3 ms 2892 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4556 KB Output is correct
2 Correct 25 ms 4572 KB Output is correct
3 Correct 60 ms 7220 KB Output is correct
4 Correct 63 ms 7368 KB Output is correct
5 Correct 133 ms 11868 KB Output is correct
6 Correct 142 ms 12032 KB Output is correct
7 Correct 126 ms 12336 KB Output is correct
8 Correct 141 ms 11736 KB Output is correct
9 Correct 168 ms 12360 KB Output is correct
10 Correct 169 ms 19240 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6184 KB Output is correct
2 Correct 27 ms 5580 KB Output is correct
3 Correct 79 ms 11304 KB Output is correct
4 Correct 72 ms 9796 KB Output is correct
5 Correct 219 ms 19856 KB Output is correct
6 Correct 143 ms 15096 KB Output is correct
7 Correct 191 ms 20288 KB Output is correct
8 Correct 186 ms 15212 KB Output is correct
9 Correct 140 ms 14080 KB Output is correct
10 Correct 148 ms 14040 KB Output is correct