oj.uz

Submission #28203

# Submission time Handle Problem Language Result Execution time Memory
28203 2017-07-15T15:20:46 Z psint Ideal city (IOI12_city) C++14
100 / 100
 923 ms 25308 KB 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 100010

int n;
const int MOD = 1000000000;

int cnt;
int W[MAXN], N[MAXN];
queue<int> Q;
set<int> E[MAXN];
map<pair<int,int>, int> M;

pair<int,int> dfs(int node, int src) {
    int total = W[node], ans = 0;
    for (auto next : E[node]) if (src != next) {
        pair<int,int> result = dfs(next, node);
        ans = (ans + result.first) % MOD;
        ans = (ans + ((long long) result.second * (long long) (n - result.second)) % MOD) % MOD;
        total += result.second;
    }
    return { ans, total };
}

int findDist(vector<int> &X, vector<int> &Y) {
    cnt = 0; M.clear();
    for (int i = 0; i < MAXN; i ++) { E[i].clear(); W[i] = 0; N[i] = -1; }

    for (int i = 0; i < n; i ++) M[{ X[i], Y[i] }] = i+1;
    for (int i = 0; i < n; i ++) if (N[i] == -1) {
        Q.push(i);
        while (!Q.empty()) {
            int node = Q.front(); Q.pop();
            if (N[node] != -1) continue;
            N[node] = cnt;
            W[cnt] ++;
            for (int diff = -1; diff <= 1; diff += 2) {
                int next = M[{ X[node], Y[node] + diff }];
                if (next != 0) Q.push(next-1);
            }
        }
        cnt ++;
    }

    for (int i = 0; i < n; i ++) for (int diff = -1; diff <= 1; diff += 2) {
        int j = M[{ X[i] + diff, Y[i] }];
        if (j != 0) E[N[i]].insert(N[j-1]);
    }

    return dfs(0, -1).first;
}


int DistanceSum(int N, int *X, int *Y) {
    n = N;

    vector<int> xs, ys;
    for (int i = 0; i < n; i ++) {
        xs.push_back(X[i]);
        ys.push_back(Y[i]);
    }

    int ansX = findDist(xs, ys);
    int ansY = findDist(ys, xs);
    return (ansX + ansY) % MOD;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9300 KB Output is correct
2 Correct 59 ms 9432 KB Output is correct
3 Correct 203 ms 11776 KB Output is correct
4 Correct 213 ms 11776 KB Output is correct
5 Correct 593 ms 15848 KB Output is correct
6 Correct 576 ms 15980 KB Output is correct
7 Correct 603 ms 16248 KB Output is correct
8 Correct 309 ms 15716 KB Output is correct
9 Correct 613 ms 16460 KB Output is correct
10 Correct 676 ms 24484 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 11148 KB Output is correct
2 Correct 79 ms 10356 KB Output is correct
3 Correct 349 ms 16264 KB Output is correct
4 Correct 326 ms 14432 KB Output is correct
5 Correct 903 ms 25088 KB Output is correct
6 Correct 606 ms 19276 KB Output is correct
7 Correct 923 ms 25308 KB Output is correct
8 Correct 659 ms 19580 KB Output is correct
9 Correct 759 ms 18356 KB Output is correct
10 Correct 599 ms 18092 KB Output is correct