oj.uz

Submission #259214

# Submission time Handle Problem Language Result Execution time Memory
259214 2020-08-07T12:09:02 Z SamAnd Ideal city (IOI12_city) C++17
100 / 100
 440 ms 16064 KB 
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005, M = 1000000000;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};

ll ans;

int n;
int X[N], Y[N];
map<pair<int, int>, int> mp;

int k;
int c[N];

void dfs(int i)
{
    if (c[i])
        return;
    c[i] = k;
    if (mp.find(m_p(X[i], Y[i] + 1)) != mp.end())
        dfs(mp[m_p(X[i], Y[i] + 1)]);
    if (mp.find(m_p(X[i], Y[i] - 1)) != mp.end())
        dfs(mp[m_p(X[i], Y[i] - 1)]);
}

int q[N];
vector<int> g[N];

void dfs1(int x, int p)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs1(h, x);
        q[x] += q[h];
    }
    ans += (q[x] * 1LL * (n - q[x]));
}

void solv()
{
    k = 0;
    memset(c, 0, sizeof c);
    for (int i = 0; i < n; ++i)
        g[i].clear();
    memset(q, 0, sizeof q);

    for (int i = 0; i < n; ++i)
    {
        if (!c[i])
        {
            ++k;
            dfs(i);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        if (mp.find(m_p(X[i] + 1, Y[i])) != mp.end())
        {
            g[c[i]].push_back(c[mp[m_p(X[i] + 1, Y[i])]]);
            g[c[mp[m_p(X[i] + 1, Y[i])]]].push_back(c[i]);
        }
    }

    for (int i = 0; i < n; ++i)
    {
        sort(all(g[i]));
        vector<int> v;
        for (int j = 0; j < sz(g[i]); ++j)
        {
            if (!j || g[i][j] != g[i][j - 1])
                v.push_back(g[i][j]);
        }
        g[i] = v;
    }

    for (int i = 0; i < n; ++i)
    {
        q[c[i]]++;
    }

    dfs1(1, 1);
}

int DistanceSum(int N, int *X_, int *Y_)
{
    n = N;
    for (int i = 0; i < n; ++i)
    {
        X[i] = X_[i];
        Y[i] = Y_[i];
    }

    int minx = X[0];
    int miny = Y[0];
    for (int i = 0; i < n; ++i)
    {
        minx = min(minx, X[i]);
        miny = min(miny, Y[i]);
    }

    for (int i = 0; i < n; ++i)
    {
        X[i] -= (minx - 1);
        Y[i] -= (miny - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        mp[m_p(X[i], Y[i])] = i;
    }

    solv();

    mp.clear();
    for (int i = 0; i < n; ++i)
    {
        swap(X[i], Y[i]);
        mp[m_p(X[i], Y[i])] = i;
    }

    solv();

    return (ans % M);
}

Compilation message

city.cpp: In function 'void dfs1(int, int)':
city.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 5624 KB Output is correct
2 Correct 51 ms 5752 KB Output is correct
3 Correct 139 ms 8568 KB Output is correct
4 Correct 169 ms 9112 KB Output is correct
5 Correct 440 ms 13944 KB Output is correct
6 Correct 406 ms 14584 KB Output is correct
7 Correct 378 ms 13944 KB Output is correct
8 Correct 376 ms 13564 KB Output is correct
9 Correct 377 ms 14216 KB Output is correct
10 Correct 344 ms 16064 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5628 KB Output is correct
2 Correct 58 ms 5744 KB Output is correct
3 Correct 160 ms 8756 KB Output is correct
4 Correct 154 ms 8824 KB Output is correct
5 Correct 414 ms 13944 KB Output is correct
6 Correct 405 ms 14076 KB Output is correct
7 Correct 414 ms 13944 KB Output is correct
8 Correct 402 ms 13944 KB Output is correct
9 Correct 423 ms 13748 KB Output is correct
10 Correct 380 ms 13944 KB Output is correct