oj.uz

Submission #821887

# Submission time Handle Problem Language Result Execution time Memory
821887 2023-08-11T19:56:30 Z annabeth9680 Ideal city (IOI12_city) C++17
0 / 100
 52 ms 5488 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 4468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 5488 KB Output isn't correct
2 Halted 0 ms 0 KB -