Submission #821891

#	Time	Username	Problem	Language	Result	Execution time	Memory
821891		annabeth9680	Ideal city (IOI12_city)	C++17	0 / 100	41 ms	5440 KiB

city

#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[cnt].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[cnt].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: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45