oj.uz

Submission #363088

# Submission time Handle Problem Language Result Execution time Memory
363088 2021-02-05T04:33:40 Z 2qbingxuan Ideal city (IOI12_city) C++14
100 / 100
 107 ms 10428 KB 
#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
    int f = 0;
    ((std::cerr << "(" << s << ") = (") , ... , (std::cerr << (f++ ? ", " : "") << args)), std::cerr << ")\n";
}
#else
#define debug(...) ((void)0)
#endif // local
using namespace std;
const int maxn = 100025, mod = 1e9;
namespace dsu {
int pa[maxn], sz[maxn];
void init(int N) {
    for (int i = 0; i < N; i++) pa[i] = i, sz[i] = 1;
}
int anc(int x) {
    return x==pa[x] ? x : pa[x] = anc(pa[x]);
}
bool join(int x, int y) {
    if ((x=anc(x)) == (y=anc(y))) return false;
    if (sz[x] < sz[y]) swap(x, y);
    return pa[y] = x, sz[x] += sz[y], true;
}
}

struct Point {
    int x, y, id;
} pts[maxn];

vector<int> tr[maxn];
bool vis[maxn];
int ds[maxn], sz[maxn];
int ans;
void dfs(int i) {
    vis[i] = true;
    sz[i] = dsu::sz[i];
    ds[i] = 0;
    debug(i, sz[i]);
    for (int j: tr[i]) {
        if (vis[j]) continue;
        dfs(j);
        ans = (ans + 1LL * sz[i] * (ds[j] + sz[j]) + 1LL * sz[j] * ds[i]) % mod;
        ds[i] = (ds[i] + ds[j] + sz[j]) % mod;
        sz[i] += sz[j];
    }
    debug(i, ds[i], sz[i]);
}
void solve(int N) {

    for (int i = 0; i < N; i++) tr[i].clear(), vis[i] = false;
    sort(pts, pts + N, [](Point a, Point b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
    dsu::init(N);
    for (int i = 1; i < N; i++) {
        if (pts[i].x == pts[i-1].x && pts[i].y == pts[i-1].y + 1)
            dsu::join(pts[i].id, pts[i-1].id);
    }
    sort(pts, pts + N, [](Point a, Point b) { return a.y != b.y ? a.y < b.y : a.x < b.x; });
    for (int i = 1; i < N; i++) {
        if (pts[i].y == pts[i-1].y && pts[i].x == pts[i-1].x + 1) {
            int a = dsu::anc(pts[i].id);
            int b = dsu::anc(pts[i-1].id);
            tr[a].push_back(b);
            tr[b].push_back(a);
        }
    }
#define sort_uni(v) sort(v.begin(),v.end()),v.erase(unique(v.begin(), v.end()), v.end())
    for (int i = 0; i < N; i++)
        sort_uni(tr[i]);
    dfs(dsu::anc(0));
    debug(dsu::anc(0));
    debug("HERE");
}
int DistanceSum(int N, int *X, int *Y) {
    ans = 0;

    for (int i = 0; i < N; i++)
        pts[i] = { X[i], Y[i], i };
    solve(N);
    for (int i = 0; i < N; i++)
        pts[i] = { Y[i], X[i], i };
    solve(N);
    return ans % mod;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3948 KB Output is correct
2 Correct 16 ms 4076 KB Output is correct
3 Correct 48 ms 5744 KB Output is correct
4 Correct 48 ms 5740 KB Output is correct
5 Correct 82 ms 8940 KB Output is correct
6 Correct 80 ms 8812 KB Output is correct
7 Correct 80 ms 8684 KB Output is correct
8 Correct 81 ms 8940 KB Output is correct
9 Correct 83 ms 8428 KB Output is correct
10 Correct 83 ms 10428 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3948 KB Output is correct
2 Correct 19 ms 4076 KB Output is correct
3 Correct 48 ms 5740 KB Output is correct
4 Correct 51 ms 5996 KB Output is correct
5 Correct 107 ms 8812 KB Output is correct
6 Correct 93 ms 9708 KB Output is correct
7 Correct 105 ms 9708 KB Output is correct
8 Correct 94 ms 9580 KB Output is correct
9 Correct 93 ms 9324 KB Output is correct
10 Correct 92 ms 9324 KB Output is correct