oj.uz

Submission #158242

# Submission time Handle Problem Language Result Execution time Memory
158242 2019-10-15T17:14:47 Z davitmarg Ideal city (IOI12_city) C++17
32 / 100
 161 ms 3448 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000000ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

int x[100005], y[100005], used[100005], d[100005], ans, n;
vector<int> g[100005];

void bfs(int v)
{
    for (int i = 1; i <= n; i++)
        used[i] = 0;
    queue<int> q;
    used[v] = 1;
    d[v] = 0;
    q.push(v);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        ans += d[v];
        ans %= mod;
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (used[to])
                continue;
            d[to] = d[v] + 1;
            used[to] = 1;
            q.push(to);
        }
    }
}

int DistanceSum(int N, int *X, int *Y)
{
    n = N;
    for (int i = 1; i <= n; i++)
    {
        x[i] = X[i - 1];
        y[i] = Y[i - 1];
    }
    if (n <= 2000)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1)
                    g[i].PB(j);
        for (int i = 1; i <= n; i++)
            bfs(i);
        ans /= 2;
    }
    else
    {
        vector<pair<int, int>> v;

        v.clear();
        for (int i = 1; i <= n; i++)
            v.PB(MP(x[i], y[i]));
        sort(all(v));
        for (int i = 1; i <= n; i++)
            if (i == 1 || v[i].first != v[i - 1].first)
            {
                ans += i - 1;
                ans %= mod;
            }

        v.clear();
        for (int i = 1; i <= n; i++)
            v.PB(MP(y[i], x[i]));
        sort(all(v));
        for (int i = 1; i <= n; i++)
            if (i == 1 || v[i].first != v[i - 1].first)
            {
                ans += i - 1;
                ans %= mod;
            }
    }

    return ans;
}

#ifdef death

int main()
{
    int N, X[102], Y[102];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> X[i] >> Y[i];
    cout << DistanceSum(N, X, Y) << endl;
    return 0;
}

#endif

/*




*/

Compilation message

city.cpp: In function 'void bfs(int)':
city.cpp:42:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2680 KB Output is correct
2 Correct 42 ms 2788 KB Output is correct
3 Correct 91 ms 2912 KB Output is correct
4 Correct 91 ms 2936 KB Output is correct
5 Correct 159 ms 2864 KB Output is correct
6 Correct 154 ms 2808 KB Output is correct
7 Correct 161 ms 2808 KB Output is correct
8 Correct 161 ms 2812 KB Output is correct
9 Correct 156 ms 2856 KB Output is correct
10 Correct 147 ms 2936 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -