oj.uz

Submission #117363

# Submission time Handle Problem Language Result Execution time Memory
117363 2019-06-15T16:26:30 Z someone_aa Ideal city (IOI12_city) C++17
100 / 100
 595 ms 45304 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
const ll mod = 1e9;
ll result;

class tree {
public:
    int usize[maxn], uparent[maxn], n;
    int value[maxn];
    ll total_sum, sbtsize[maxn];
    vector<int>g[maxn];

    void init(int _n) {
        n = _n;
        for(int i=1;i<=n;i++) {
            usize[i] = 1;
            uparent[i] = i;
        }
    }
    int ufind(int x) {
        while(x != uparent[x]) {
            x = uparent[x];
        }
        return x;
    }
    void add_edge(int x, int y) {
        g[x].pb(y);
        g[y].pb(x);
    }
    void unite(int x, int y) {
        int _x = x, _y = y;
        x = ufind(x);
        y = ufind(y);

        if(x == y) return;
        add_edge(_x, _y);

        if(usize[x] > usize[y]) {
            uparent[y] = x;
            usize[x] += usize[y];
        }
        else {
            uparent[x] = y;
            usize[y] += usize[x];
        }
    }
    void init_dfs() {
        for(int i=1;i<=n;i++) {
            total_sum += value[i];
        }
    }
    void dfs(int node, int p) {
        sbtsize[node] = value[node];
        for(int i:g[node]) {
            if(i != p) {
                dfs(i, node);
                result += sbtsize[i] * (total_sum - sbtsize[i]);
                result %= mod;
                sbtsize[node] += sbtsize[i];
            }
        }
    }
}t1, t2;

map<pair<int,int>, int> rcomp, ccomp;
map<pair<int,int>, bool> exist;
set<int> rs, cs;
map<int,set<int> > r, c;

int DistanceSum(int N, int *X, int *Y) {
    for(int i=0;i<N;i++) {
        rs.insert(X[i]);
        cs.insert(Y[i]);
        exist[mp(X[i], Y[i])] = true;
        r[X[i]].insert(Y[i]);
        c[Y[i]].insert(X[i]);
    }

    t1.init(N);
    t2.init(N);
    int br = 0;
    for(auto i:rs) {
        for(int j:r[i]) {
            int cx = i;
            int cy = j;

            if(!exist[mp(cx, cy-1)])
                br++;
            rcomp[mp(cx, cy)] = br;
            t1.value[br]++;

            if(exist[mp(cx-1, cy)]) {
                t1.unite(rcomp[mp(cx-1, cy)], br);
            }
        }
    }

    br = 0;
    for(auto i:cs) {
        for(int j:c[i]) {
            int cx = j;
            int cy = i;

            if(!exist[mp(cx-1, cy)])
                br++;
            ccomp[mp(cx, cy)] = br;
            t2.value[br]++;

            if(exist[mp(cx, cy-1)]) {
                t2.unite(ccomp[mp(cx, cy-1)], br);
            }
        }
    }

    t1.init_dfs();
    t2.init_dfs();
    t1.dfs(1, -1);
    t2.dfs(1, -1);
    return result;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11456 KB Output is correct
2 Correct 64 ms 11536 KB Output is correct
3 Correct 211 ms 20984 KB Output is correct
4 Correct 207 ms 21240 KB Output is correct
5 Correct 523 ms 36748 KB Output is correct
6 Correct 547 ms 36856 KB Output is correct
7 Correct 505 ms 37624 KB Output is correct
8 Correct 506 ms 36728 KB Output is correct
9 Correct 543 ms 37368 KB Output is correct
10 Correct 595 ms 45304 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 13068 KB Output is correct
2 Correct 80 ms 12424 KB Output is correct
3 Correct 250 ms 24860 KB Output is correct
4 Correct 233 ms 23416 KB Output is correct
5 Correct 567 ms 44264 KB Output is correct
6 Correct 558 ms 39840 KB Output is correct
7 Correct 588 ms 44576 KB Output is correct
8 Correct 551 ms 39952 KB Output is correct
9 Correct 536 ms 39004 KB Output is correct
10 Correct 497 ms 38648 KB Output is correct