oj.uz

Submission #17168

# Submission time Handle Problem Language Result Execution time Memory
17168 2015-11-07T13:24:43 Z murat Ideal city (IOI12_city) C++
100 / 100
 114 ms 16884 KB 
#include<bits/stdc++.h>

using namespace std;

#define type(x) __typeof(x.begin())
#define foreach(it, x) for(type(x) it = x.begin(); it != x.end(); it++)
#define mp make_pair
#define pb push_back
#define nd second
#define st first

const int N = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 1e9;

typedef pair< int , int > pii;

int n, m, x, y, z, t, size[N], root[N];
map< int , vector< int > > D, Y;
vector< int > v[N];
int sum[N];

int findset(int x) { return root[x] = root[x] == x ? x : findset(root[x]); }

int merge(int x, int y) {
    v[x].pb(y);
    v[y].pb(x);
}

int dfs(int node, int root = 0) {
    int all = 0;
    foreach(it, v[node]) {
        if(*it == root) continue;
        all = (all + dfs(*it, node)) % mod;
        sum[node] += sum[*it];
    }
    return (all + (long long) sum[node] * (n - sum[node])) % mod;
}

int solve() {
    map< pii , int > dp;
    int all = 0, ty = -5;
    int S = 0;
    vector< pair< pii , int > > tt;
    foreach(it, D) {
        vector< int > &v = (it->nd);
        vector< pair< pii , int > > l;
        int yy = it->st;
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++) {
            int oo = i;
            while(i + 1 < v.size() && v[i] + 1 == v[i+1])
                i++;
            l.pb(mp(mp(v[oo], v[i]), ++S));
            ::v[S].clear();
            sum[S] = l.back().st.nd - l.back().st.st + 1;
        }
        if(ty + 1 == yy) {
            int j = 0;
            foreach(it, l) {
                while(tt[j].st.nd < it->st.st && j < tt.size()) {
                    j++;
                }
                while(tt[j].st.st <= it->st.nd && j < tt.size()) {
                    merge(tt[j].nd, it->nd);
                    j++;
                } if(j) j--;
            }
        }
        foreach(it, l) {
            int sz = size[findset(it->nd)];
            all = (all +  sz * (long long) (n - sz));
        }
        tt = l;
        ty = yy;
    }

    return dfs(1);
}

int DistanceSum(int N, int *X, int *Y) {

    n = N;
    for(int i = 0; i < N; i++) {
        int x = X[i], y = Y[i];
        ::D[y].pb(x);
        ::Y[x].pb(y);
    }

    int ans = solve();

    ::D.clear(); ::Y.clear();

    for(int i = 0; i < N; i++) {
        int y = X[i], x = Y[i];
        ::D[y].pb(x);
        ::Y[x].pb(y);
    }

    ans = (ans + solve()) % mod;

    return ans;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9356 KB Output is correct
2 Correct 15 ms 9356 KB Output is correct
3 Correct 35 ms 9936 KB Output is correct
4 Correct 35 ms 9956 KB Output is correct
5 Correct 73 ms 11144 KB Output is correct
6 Correct 67 ms 11180 KB Output is correct
7 Correct 76 ms 11244 KB Output is correct
8 Correct 64 ms 11120 KB Output is correct
9 Correct 77 ms 11100 KB Output is correct
10 Correct 114 ms 16884 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9620 KB Output is correct
2 Correct 18 ms 9492 KB Output is correct
3 Correct 44 ms 10596 KB Output is correct
4 Correct 39 ms 10508 KB Output is correct
5 Correct 95 ms 12436 KB Output is correct
6 Correct 84 ms 11680 KB Output is correct
7 Correct 97 ms 12456 KB Output is correct
8 Correct 81 ms 11728 KB Output is correct
9 Correct 65 ms 11380 KB Output is correct
10 Correct 76 ms 11384 KB Output is correct