oj.uz

Submission #169862

# Submission time Handle Problem Language Result Execution time Memory
169862 2019-12-23T05:22:32 Z tri Ideal city (IOI12_city) C++14
100 / 100
 226 ms 15404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const ll MOD = 1e9;
const int MAXN = 1e5 + 10;

int N;
vector<pi> pts;
map<pi, int> comp;

int nC = 0;

ll ans = 0;

int sz[MAXN];
vi aL[MAXN];

int dX[] = {-1, 0, 1, 0};
int dY[] = {0, -1, 0, 1};

int dfs(int cV, int pV) {
    int cSz = sz[cV];
    for (int aV : aL[cV]) {
        if (aV != pV) {
            cSz += dfs(aV, cV);
        }
    }
//    ps(cV, cSz);
    ans = (ans + (ll) cSz * (N - cSz)) % MOD;
    return cSz;
}

void sumV() {
    comp.clear();
    nC = 0;

    memset(sz, 0, sizeof(sz));
    for (int i = 0; i < N; i++) {
        aL[i].clear();
    }

    sort(pts.begin(), pts.end());
//    ps(pts);

    for (int i = 0; i < N; i++) {
        if (i > 0 && pts[i].f == pts[i - 1].f && pts[i].s == pts[i - 1].s + 1) { // one above previous
            comp[pts[i]] = nC - 1;
            sz[nC - 1]++;
        } else {
            comp[pts[i]] = nC++;
            sz[nC - 1]++;
        }
    }

    for (int i = 0; i < N; i++) {
        pi left = {pts[i].f - 1, pts[i].s};
        if (comp.count(left)) {
            int cC = comp[pts[i]];
            int aC = comp[left];
            aL[cC].pb(aC);
            aL[aC].pb(cC);
        }
    }

    for (int i = 0; i < N; i++) {
        aL[i].erase(unique(aL[i].begin(), aL[i].end()), aL[i].end());
    }

//    ps("debug graph");
//    for (int i = 0; i < N; i++) {
//        ps(pts[i]);
//        ps(comp[pts[i]]);
//    }
//
//    for (int i = 0; i < nC; i++) {
//        ps(sz[i]);
//    }
//
//    for (int i = 0; i < nC; i++) {
//        ps(aL[i]);
//    }
//
//    ps("fin");

    for (int i = 0; i < nC; i++) {
        if (aL[i].size() == 1) {
            dfs(i, -1);
            break;
        }
    }
}

int DistanceSum(int iN, int *X, int *Y) {
    N = iN;
    for (int i = 0; i < N; i++) {
        pts.pb({X[i], Y[i]});
    }

    sumV();
//    ps(ans);

    for (int i = 0; i < N; i++) {
        swap(pts[i].f, pts[i].s);
    }
    sumV();
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4980 KB Output is correct
2 Correct 38 ms 5208 KB Output is correct
3 Correct 104 ms 7668 KB Output is correct
4 Correct 105 ms 8052 KB Output is correct
5 Correct 221 ms 12372 KB Output is correct
6 Correct 223 ms 14064 KB Output is correct
7 Correct 226 ms 13808 KB Output is correct
8 Correct 222 ms 13040 KB Output is correct
9 Correct 225 ms 13676 KB Output is correct
10 Correct 214 ms 15404 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4976 KB Output is correct
2 Correct 38 ms 5108 KB Output is correct
3 Correct 101 ms 7924 KB Output is correct
4 Correct 105 ms 8052 KB Output is correct
5 Correct 210 ms 12656 KB Output is correct
6 Correct 220 ms 13608 KB Output is correct
7 Correct 210 ms 13552 KB Output is correct
8 Correct 219 ms 13564 KB Output is correct
9 Correct 220 ms 13420 KB Output is correct
10 Correct 220 ms 13552 KB Output is correct