제출 #1238774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238774		guanex	Ideal city (IOI12_city)	C++20	100 / 100	339 ms	25240 KiB

city

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int mod = 1e9;

int cntx[100000 + 10];

ll ans = 0;

ll n = 0;

int vis[100000 + 10];

ll dfs(int no, int fat, vector<vector<int>> &ed){
  ll nodessum = cntx[no];
  //cout << no << " " << fat << endl;
  vis[no] = 1;
  for(auto e:ed[no]){
    if(e == fat || vis[e] == 1)continue;
    ll su = dfs(e, no, ed);
    nodessum += su;
    ans += (n - su) * (su);
    ans %= mod;
  }
  return nodessum;
}

void coordinate(map<pair<int, int>, int> &nodesy){
  int cnt = 0;
  pair<int, int> last = {-1, -1};
  map<int, int> bigx;
  memset(cntx, 0, sizeof cntx);
  memset(vis, 0, sizeof vis);
  for(auto e:nodesy){
    if(last == (pair<int, int>){-1, -1}){
      last = e.first;
      bigx[e.second] = cnt;
      cntx[cnt]++;
      continue;
    }else{
      if(last.first == e.first.first &&last.second == e.first.second-1){
        bigx[e.second] = cnt;
        cntx[cnt]++;
        last = e.first;
      }else{
        cnt++;
        last = e.first;
        bigx[e.second] = cnt;
        cntx[cnt]++;
      }
    }
  }
  vector<vector<int>> edx(100005);
  int start = 0;
  for(auto e:nodesy){
    int truenode = bigx[e.second];
    start = truenode;
    if(nodesy.count((pair<int, int>){e.first.first+1, e.first.second})){
      edx[truenode].push_back(bigx[nodesy[{e.first.first+1, e.first.second}]]);
    }
    if(nodesy.count((pair<int, int>){e.first.first-1, e.first.second})){
      edx[truenode].push_back(bigx[nodesy[{e.first.first-1, e.first.second}]]);
    }
  }
  dfs(start, -1, edx);
  //cout << ans << endl;
}

int DistanceSum(int N, int *X, int *Y) {
  n = N;
  memset(cntx, 0, sizeof cntx);
  memset(vis, 0, sizeof vis);
  map<pair<int, int>, int> nodesx;
  map<pair<int, int>, int> nodesy;
  for(int i = 0; i < N; ++i){
    nodesx[{X[i], Y[i]}] = i;
    nodesy[{Y[i], X[i]}] = i;
  }
  coordinate(nodesy);
  coordinate(nodesx);
  return ans % mod;
}

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