Submission #220371

#	Time	Username	Problem	Language	Result	Execution time	Memory
220371		FieryPhoenix	Ideal city (IOI12_city)	C++11	23 / 100	295 ms	15992 KiB

city

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000000

int N,X[100001],Y[100001];
int minX=INF,minY=INF;
map<pair<int,int>,int>mp; 
vector<int>row[100005],col[100005];
ll ans;
int rt[100005],siz[100005];

void reset(){
  for (int i=0;i<N;i++){
    rt[i]=i;
    siz[i]=1;
  }
}

int root(int x){
  while (x!=rt[x]){
    rt[x]=rt[rt[x]];
    x=rt[x];
  }
  return x;
}

void merge(int a, int b){
  a=root(a);
  b=root(b);
  if (a==b) return;
  if (siz[a]<siz[b]) swap(a,b);
  rt[b]=a;
  siz[a]+=siz[b];
}

void sweepRow(){
  reset();
  for (int i=1;i<=N;i++){
    for (int j:row[i]){
      if (X[j]>1 && mp.count({X[j]-1,Y[j]}))
	merge(j,mp[{X[j]-1,Y[j]}]);
      if (Y[j]>1 && mp.count({X[j],Y[j]-1}))
	merge(j,mp[{X[j],Y[j]-1}]);
      if (Y[j]<N && mp.count({X[j],Y[j]+1}))
	merge(j,mp[{X[j],Y[j]+1}]);
    }
    set<int>s;
    for (int j:row[i])
      s.insert(root(j));
    for (int x:s){
      ans+=(ll)siz[x]*(N-siz[x]);
    }
    ans%=MOD;
  }
}

void sweepCol(){
  reset();
  for (int i=1;i<=N;i++){
    for (int j:col[i]){
      if (X[j]>1 && mp.count({X[j]-1,Y[j]}))
	merge(j,mp[{X[j]-1,Y[j]}]);
      if (X[j]<N && mp.count({X[j]+1,Y[j]}))
	merge(j,mp[{X[j]+1,Y[j]}]);
      if (Y[j]>1 && mp.count({X[j],Y[j]-1}))
	merge(j,mp[{X[j],Y[j]-1}]);
    }
    set<int>s;
    for (int j:col[i])
      s.insert(root(j));
    for (int x:s){
      ans+=(ll)siz[x]*(N-siz[x]);
    }
    ans%=MOD;
  }
}

int DistanceSum(int n, int x[], int y[]){
  N=n;
  for (int i=0;i<N;i++){
    X[i]=x[i];
    Y[i]=y[i];
    minX=min(minX,X[i]);
    minY=min(minY,Y[i]);
  }
  for (int i=0;i<N;i++){
    X[i]-=(minX-1);
    Y[i]-=(minY-1);
    mp[{X[i],Y[i]}]=i;
    row[X[i]].push_back(i);
    col[Y[i]].push_back(i);
  }
  sweepRow();
  sweepCol();
  return ans;
}

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