oj.uz

Submission #289943

# Submission time Handle Problem Language Result Execution time Memory
289943 2020-09-03T08:52:56 Z ToMmyDong Ideal city (IOI12_city) C++11
100 / 100
 504 ms 19064 KB 
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define ALL(i) i.begin(), i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& __printRng (ostream& os, IT bg, IT ed) {
    for (IT it=bg;it!=ed;it++) {
        if (it == bg) os << "{" << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T> &vec) {
    return __printRng(os, ALL(vec));
}
template<typename T> ostream& operator << (ostream& os, const set<T> &vec) {
    return __printRng(os, ALL(vec));
}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S> &pa) {
    return os << "{" << pa.X << "," << pa.Y << "}";
}
#else
#define debug(...)
#endif

const int MAXN = 100083;
const int MOD = 1000000000;

int add (int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}

int sub (int x, int y) {
    x -= y;
    return x < 0 ? x + MOD : x;
}

int mul (int x, int y) {
    return ll(x) * y % MOD;
}

map<pii, int> id;
int djs[MAXN], sz[MAXN];
int fnd (int x) {
    return djs[x] == x ? x : djs[x] = fnd(djs[x]);
}

void mrg (int x, int y) {
    x = fnd(x), y = fnd(y);
    if (x == y) return;
    djs[x] = y;
    sz[y] += sz[x];
}

set<int> edge[MAXN];

int ssum[MAXN], N;
int dfs (int nd, int par) {
    ssum[nd] = sz[nd];
    int res = 0;
    for (int v : edge[nd]) {
        if (v != par) {
            res = add(res, dfs(v, nd));
            ssum[nd] += ssum[v];
            debug(nd, v, ssum[v]);
            res = add(res, mul(ssum[v], N-ssum[v]));
        }
    }
    debug(nd, res, sz[nd]);
    return res;
}
int oneDirection (int n, int *x, int *y) {
    N = n;
    id.clear();
    for (int i=0; i<n; i++) djs[i] = i, sz[i] = 1;
    for (int i=0; i<n; i++) edge[i].clear(); 
    for (int i=0; i<n; i++) id[pii(x[i], y[i])] = i;

    for (int i=0; i<n; i++) {
        if (id.count({x[i]+1, y[i]})) {
            mrg(i, id[pii(x[i]+1, y[i])]);
        }
    }

    for (int i=0; i<n; i++) {
        if (id.count({x[i], y[i]+1})) {
            int uid = fnd(id[pii(x[i], y[i]+1)]);
            int vid = fnd(i);
            edge[vid].insert(uid);
            edge[uid].insert(vid);
        }
    }

    for (int i=0; i<n; i++) {
        debug(edge[i]);
        debug(sz[i]);
    }

    for (int i=0; i<n; i++) {
        if (fnd(i) == i) {
            return dfs(i, -1);
        }
    }
    return -1;
}

int DistanceSum(int n, int *x, int *y) {
    return add(oneDirection(n, x, y), oneDirection(n, y, x));
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7032 KB Output is correct
2 Correct 51 ms 6912 KB Output is correct
3 Correct 151 ms 9720 KB Output is correct
4 Correct 146 ms 9720 KB Output is correct
5 Correct 485 ms 14128 KB Output is correct
6 Correct 442 ms 14328 KB Output is correct
7 Correct 472 ms 14584 KB Output is correct
8 Correct 469 ms 14072 KB Output is correct
9 Correct 504 ms 14584 KB Output is correct
10 Correct 446 ms 19064 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7680 KB Output is correct
2 Correct 56 ms 7416 KB Output is correct
3 Correct 170 ms 11512 KB Output is correct
4 Correct 167 ms 10872 KB Output is correct
5 Correct 483 ms 18040 KB Output is correct
6 Correct 475 ms 15864 KB Output is correct
7 Correct 496 ms 18168 KB Output is correct
8 Correct 486 ms 15924 KB Output is correct
9 Correct 466 ms 15352 KB Output is correct
10 Correct 474 ms 15224 KB Output is correct