Submission #220517

#	Time	Username	Problem	Language	Result	Execution time	Memory
220517		FieryPhoenix	Ideal city (IOI12_city)	C++11	0 / 100	79 ms	10360 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];
vector<int>adj[100005];
ll subsize[100005];
bool vis[100005];

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

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 dfs(int node, int par){
  vis[node]=true;
  cout<<node<<endl;
  subsize[node]=siz[node];
  for (int x:adj[node])
    if (x!=par && !vis[x]){
      dfs(x,node);
      subsize[node]+=subsize[x];
    }
  if (node!=par){
    ans+=subsize[node]*(N-subsize[node]);
    ans%=MOD;
  }
}
      
void solveRow(){
  reset();
  for (int i=1;i<=N;i++)
    for (int j:row[i]){
      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}]);
    }
  for (int i=1;i<=N;i++)
    for (int j:row[i]){
      if (X[j]>1 && mp.count({X[j]-1,Y[j]})){
	int a=root(j);
	int b=root(mp[{X[j]-1,Y[j]}]);
	adj[a].push_back(b);
	adj[b].push_back(a);
      }
    }
  dfs(root(0),root(0));
}

void solveCol(){
  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]}]);
    }
  for (int i=1;i<=N;i++)
    for (int j:col[i]){
      if (Y[j]>1 && mp.count({X[j],Y[j]-1})){
	int a=root(j);
	int b=root(mp[{X[j],Y[j]-1}]);
	adj[a].push_back(b);
	adj[b].push_back(a);
      }
    }
  dfs(root(0),root(0));
}

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);
  }
  solveRow();
  solveCol();
  return ans;
}

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