oj.uz

Submission #363086

# Submission time Handle Problem Language Result Execution time Memory
363086 2021-02-05T04:32:20 Z 2qbingxuan Ideal city (IOI12_city) C++14
32 / 100
 297 ms 4332 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]) + sz[j] * ds[i]) % mod;
        ds[i] += ds[j] + sz[j];
        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);
    }
    for (int i = 0; i < N; i++) if(i == dsu::anc(i)) {
        int x = 7122;
        for (int j = 0; j < N; j++) if (pts[j].id == i) x = pts[j].x;
        debug(i, dsu::sz[i], x);
    }
    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]);
    for (int i = 0; i < N; i++) if(tr[i].size())
        for (int j: tr[i])
            cerr << i << ' ' << j << endl;
    // for (int s = 0; s < N; s++) {
    //     for (int j = 0; j < N; j++) vis[j] = false;
    //     dep[s] = 0;
    //     dfs(s);
    //     for (int j = 0; j < s; j++) if(vis[j]) ans += dsu::sz[s] * dsu::sz[j] * dep[j];
    // }
    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;

}

Compilation message

city.cpp: In function 'void solve(int)':
city.cpp:60:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   60 |         int x = 7122;
      |             ^

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 3 ms 2668 KB Output is correct
6 Correct 5 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 5 ms 2668 KB Output is correct
9 Correct 4 ms 2668 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2796 KB Output is correct
2 Correct 11 ms 2796 KB Output is correct
3 Correct 23 ms 2796 KB Output is correct
4 Correct 16 ms 2796 KB Output is correct
5 Correct 31 ms 2796 KB Output is correct
6 Correct 14 ms 2816 KB Output is correct
7 Correct 32 ms 2924 KB Output is correct
8 Correct 15 ms 2796 KB Output is correct
9 Correct 13 ms 2796 KB Output is correct
10 Correct 12 ms 2796 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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