Submission #821887

#	Time	Username	Problem	Language	Result	Execution time	Memory
821887		annabeth9680	Ideal city (IOI12_city)	C++17	0 / 100	52 ms	5488 KiB

city

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+25;
const int 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){
    if(node.find(p) == node.end()){
        return -1;
    }
    return node[p];
}
int DistanceSum(int N, int *X, int *Y){
    long long ans = 0;
    for(int i = 0;i<N;++i){
        pos[i].first = X[i];
        pos[i].second = Y[i];
    }
    for(int id = 0;id<2;++id){
        edges.clear(); node.clear();
        for(int i = 0;i<N;++i){
            adj[i].clear();
            node[make_pair(pos[i].first,pos[i].second)] = -2;
        }
        sort(pos,pos+N,cmp);
        int cnt = 0;
        for(int i = 0;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[cnt].second-range[cnt].first+1;
            }
        }
        for(int i = 0;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 = 0;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