Submission #1208924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208924		HappyCapybara	Ideal city (IOI12_city)	C++20	100 / 100	100 ms	15616 KiB

city

#include<bits/stdc++.h>
using namespace std;

#define ll long long

int n;

ll res;

void dfs(int cur, vector<vector<int>>& g, vector<int>& st, vector<int>& s){
    st[cur] = s[cur];
    for (int next : g[cur]){
        if (st[next] != -1) continue;
        dfs(next, g, st, s);
        st[cur] += st[next];
        res += (ll)(n-st[next])*(ll)st[next];
    }
}

ll solve(map<int,vector<int>>& m){
    int cur = -1;
    vector<int> s;
    vector<vector<int>> g;
    map<pair<int,int>,int> cc;
    for (auto [x, v] : m){
        sort(v.begin(), v.end());
        for (int i=0; i<v.size(); i++){
            if (i == 0 || v[i] != v[i-1]+1){
                cur++;
                s.push_back(0);
                g.push_back({});
            }
            cc[{x, v[i]}] = cur;
            s.back()++;
            if (x != m.begin()->first){
                if (cc.find({x-1, v[i]}) != cc.end() && (g[cur].empty() || cc[{x-1, v[i]}] != g[cur].back())){
                    g[cur].push_back(cc[{x-1, v[i]}]);
                    g[cc[{x-1, v[i]}]].push_back(cur);
                }
            }
        }
    }
    vector<int> st(cur+1, -1);
    res = 0;
    dfs(0, g, st, s);
    return res;
}

int DistanceSum(int N, int *X, int *Y){
  n = N;
  map<int,vector<int>> rows, cols;
  for (int i=0; i<N; i++){
    rows[X[i]].push_back(Y[i]);
    cols[Y[i]].push_back(X[i]);
  }
  return (solve(rows)+solve(cols)) % 1000000000;
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45