oj.uz

Submission #237713

# Submission time Handle Problem Language Result Execution time Memory
237713 2020-06-08T12:28:05 Z nicolaalexandra Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 14840 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
#define MOD 1000000000
using namespace std;

map <pair<int,int>,int> a;
set <int> L[DIM],L2[DIM];
deque <int> c;
pair <int,int> v[DIM];
int what_comp[DIM],what_comp2[DIM],Size[DIM],Size2[DIM],dist[DIM],viz[DIM];
int nr_nodes, nr_nodes2;
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};

int bfs (int start){
    int i;
    for (i=1;i<=nr_nodes;i++)
        dist[i] = INF;
    c.clear();
    c.push_back(start);
    dist[start] = 0;
    int sol = 0;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : L[nod]){
            if (dist[vecin] == INF){
                dist[vecin] = 1 + dist[nod];
                sol += 1LL * dist[vecin] * Size[vecin] % MOD;
                c.push_back(vecin);
            }}}
    return sol;
}
int bfs2 (int start){
    int i;
    for (i=1;i<=nr_nodes2;i++)
        dist[i] = INF;
    c.clear();
    c.push_back(start);
    dist[start] = 0;
    int sol = 0;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();
        for (auto vecin : L2[nod]){
            if (dist[vecin] == INF){
                dist[vecin] = 1 + dist[nod];
                sol += 1LL * dist[vecin] * Size2[vecin] % MOD;
                c.push_back(vecin);
            }}}
    return sol;
}

int DistanceSum (int n, int *X, int *Y){
    int i, sol = 0;
    for (i=1;i<=n;i++){
        v[i] = make_pair (X[i-1],Y[i-1]);
        a[v[i]] = i;
    }

    /// grupez celulele pe orizontala si pe verticala si o sa am 2 arbori


    /// orizontala
    for (i=1;i<=n;i++){
        if (!viz[i]){
            viz[i] = 1;
            what_comp[i] = ++nr_nodes;

            int x = v[i].first, y = v[i].second, cnt = 1;
            while (a[make_pair(x,y+1)]){
                y++, cnt++;
                int idx = a[make_pair(x,y)];
                viz[idx] = 1;
                what_comp[idx] = nr_nodes;
            }

            y = v[i].second;
            while (a[make_pair(x,y-1)]){
                y--, cnt++;
                int idx = a[make_pair(x,y)];
                viz[idx] = 1;
                what_comp[idx] = nr_nodes;
            }

            Size[nr_nodes] = cnt;
        }
    }

    /// construiesc primul arbore
    for (i=1;i<=n;i++){
        int ic = v[i].first, jc = v[i].second;
        int x = what_comp[i];
        for (int dir=0;dir<=3;dir++){
            int iv = ic + di[dir];
            int jv = jc + dj[dir];
            int idx = a[make_pair(iv,jv)];
            if (!idx)
                continue;
            int y = what_comp[idx];

            if (x != y){
                L[x].insert(y);
                L[y].insert(x);
            }}}

    /// verticala
    memset (viz,0,sizeof viz);
    for (i=1;i<=n;i++){
        if (!viz[i]){
            viz[i] = 1;
            what_comp2[i] = ++nr_nodes2;

            int x = v[i].first, y = v[i].second, cnt = 1;
            while (a[make_pair(x-1,y)]){
                x--, cnt++;
                int idx = a[make_pair(x,y)];
                viz[idx] = 1;
                what_comp2[idx] = nr_nodes2;
            }
            x = v[i].first;
            while (a[make_pair(x+1,y)]){
                x++, cnt++;
                int idx = a[make_pair(x,y)];
                viz[idx] = 1;
                what_comp2[idx] = nr_nodes2;
            }

            Size2[nr_nodes2] = cnt;
        }
    }

    for (i=1;i<=n;i++){
        int ic = v[i].first, jc = v[i].second;
        int x = what_comp2[i];
        for (int dir=0;dir<=3;dir++){
            int iv = ic + di[dir];
            int jv = jc + dj[dir];
            int idx = a[make_pair(iv,jv)];
            if (!idx)
                continue;
            int y = what_comp2[idx];

            if (x != y){
                L2[x].insert(y);
                L2[y].insert(x);
            }}}

    /// stiu ca o sa iau tle
    for (i=1;i<=nr_nodes;i++)
        sol = (sol + 1LL * Size[i] * bfs(i) % MOD) % MOD;

    for (i=1;i<=nr_nodes2;i++)
        sol = (sol + 1LL * Size2[i] * bfs2(i) % MOD) % MOD;

    return sol / 2;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10368 KB Output is correct
2 Correct 16 ms 10368 KB Output is correct
3 Correct 35 ms 10616 KB Output is correct
4 Correct 21 ms 10368 KB Output is correct
5 Correct 53 ms 10624 KB Output is correct
6 Correct 20 ms 10496 KB Output is correct
7 Correct 57 ms 10624 KB Output is correct
8 Correct 22 ms 10368 KB Output is correct
9 Correct 18 ms 10368 KB Output is correct
10 Correct 17 ms 10496 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12152 KB Output is correct
2 Incorrect 76 ms 12152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 14840 KB Time limit exceeded
2 Halted 0 ms 0 KB -