oj.uz

Submission #821896

# Submission time Handle Problem Language Result Execution time Memory
821896 2023-08-11T20:04:37 Z annabeth9680 Ideal city (IOI12_city) C++17
100 / 100
 284 ms 17088 KB 
#include <bits/stdc++.h>
using namespace std;
//find sum of distances
//ranges of blocks in columns/rows can be seen as nodes in a tree
//adjacent if they are connected in the real city, weight of node = number of cells in its range
//formula for sum = sum of distances between each pair of blocks = number of cells in range 1 * number in range 2 * distance horizontally
//end formula = S(e) * S'(e) with e as every edge in the graph and the two sums the sums over weights in the two compartments the tree is divided into
const int MAXN = 1e5+25;
const long long MOD = 1e9;
pair<int,int> pos[MAXN],range[MAXN];
int sum[MAXN];
vector<int> adj[MAXN];
map<pair<int,int>,int> node;
set<pair<int,int>> edges;
bool cmp(pair<int,int> x, pair<int,int> y){
    return x.second<y.second;
}
void dfs(int u, int p){
    for(auto v : adj[u]){
        if(v != p){
            dfs(v,u);
            sum[u] += sum[v];
        }
    }
}
int finden(pair<int,int> p){
    auto it = node.find(p);
    if(it == node.end()){
        return -1;
    }
    return it->second;
}
int DistanceSum(int N, int *X, int *Y){
    long long ans = 0;
    for(int i = 1;i<=N;++i){
        pos[i].first = X[i-1];
        pos[i].second = Y[i-1];
    }
    for(int id = 0;id<2;++id){
        edges.clear(); node.clear();
        for(int i = 1;i<=N;++i){
            adj[i].clear();
            node[make_pair(pos[i].first,pos[i].second)] = -2;
        }
        sort(pos+1,pos+N+1,cmp);
        int cnt = 0;
        for(int i = 1;i<=N;++i){
            int it = finden(make_pair(pos[i].first,pos[i].second-1));
            if(it == -1){
                it = ++cnt;
                range[it].first = pos[i].second;
            }
            node[make_pair(pos[i].first,pos[i].second)] = it;
            if(finden(make_pair(pos[i].first,pos[i].second+1)) == -1){
                range[it].second = pos[i].second;
                sum[it] = range[it].second-range[it].first+1;
            }
        }
        for(int i = 1;i<=N;++i){
            int it = finden(make_pair(pos[i].first,pos[i].second));
            int it2 = finden(make_pair(pos[i].first-1,pos[i].second));
            if(it != -1 && it2 != -1){
                edges.emplace(it,it2);
                edges.emplace(it2,it);
            }
        }
        for(auto p : edges) adj[p.first].push_back(p.second);
        dfs(1,-1);
        for(int i = 1;i<=cnt;++i) ans += 1LL*sum[i]*(sum[1]-sum[i]);
        for(int i = 1;i<=N;++i) swap(pos[i].first,pos[i].second);
    }
    ans %= MOD;
    return ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 4 ms 2788 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 5 ms 2932 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 5 ms 2804 KB Output is correct
10 Correct 4 ms 2800 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4328 KB Output is correct
2 Correct 40 ms 4452 KB Output is correct
3 Correct 113 ms 7100 KB Output is correct
4 Correct 112 ms 7112 KB Output is correct
5 Correct 244 ms 11432 KB Output is correct
6 Correct 268 ms 11516 KB Output is correct
7 Correct 213 ms 11816 KB Output is correct
8 Correct 262 ms 11292 KB Output is correct
9 Correct 254 ms 11836 KB Output is correct
10 Correct 259 ms 16980 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5324 KB Output is correct
2 Correct 38 ms 5096 KB Output is correct
3 Correct 120 ms 9700 KB Output is correct
4 Correct 116 ms 8824 KB Output is correct
5 Correct 272 ms 16852 KB Output is correct
6 Correct 274 ms 13660 KB Output is correct
7 Correct 277 ms 17088 KB Output is correct
8 Correct 242 ms 13728 KB Output is correct
9 Correct 263 ms 13068 KB Output is correct
10 Correct 284 ms 12828 KB Output is correct