oj.uz

Submission #363079

# Submission time Handle Problem Language Result Execution time Memory
363079 2021-02-05T04:18:50 Z 2qbingxuan Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 3820 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 dep[maxn];
void dfs(int i) {
    vis[i] = true;
    for (int j: tr[i]) {
        if (vis[j]) continue;
        dep[j] = dep[i] + 1;
        dfs(j);
    }
}
int ans;
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;
        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()) {
    //     cerr << i << " -> ";
    //     for (int j: tr[i]) cerr << j << ' ';
    //     cerr << '\n';
    // }
    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(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:54:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   54 |         int x;
      |             ^

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 2 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 3 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 9 ms 2796 KB Output is correct
2 Correct 7 ms 2796 KB Output is correct
3 Correct 19 ms 2924 KB Output is correct
4 Correct 12 ms 2924 KB Output is correct
5 Correct 33 ms 2796 KB Output is correct
6 Correct 15 ms 2796 KB Output is correct
7 Correct 35 ms 2816 KB Output is correct
8 Correct 15 ms 2796 KB Output is correct
9 Correct 14 ms 2796 KB Output is correct
10 Correct 14 ms 2796 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 45.0

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