Submission #1016328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016328		amirhoseinfar1385	Ideal city (IOI12_city)	C++17	100 / 100	204 ms	24392 KiB

city

#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long n,mod=1e9,vis[maxn];
vector<pair<long long,long long>>all;
vector<long long>adj[maxn],adja[maxn];
map<pair<long long,long long>,long long>mp;
long long mainres=0;

struct dsu{
  long long par[maxn],sz[maxn];
  dsu(){
    for(long long i=0;i<maxn;i++){
      par[i]=i;
      sz[i]=1;
    }
  }
  long long root(long long u){
    if(u==par[u]){
      return u;
    }
    return par[u]=root(par[u]);
  }
  long long con(long long u,long long v){
    long long rootu=root(u),rootv=root(v);
    if(rootu!=rootv){
      par[rootu]=rootv;
      sz[rootv]+=sz[rootu];
      sz[rootu]=0;
      return 1;
    }
    return 0;
  }
}ds1,ds2;

long long dfs(long long u,long long par=-1){
  vis[u]=ds1.sz[u];
  sort(adj[u].begin(),adj[u].end());
  adj[u].resize(unique(adj[u].begin(),adj[u].end())-adj[u].begin());
  long long ret=ds1.sz[u];
  for(auto x:adj[u]){
    if(x!=par){
      ret+=dfs(x,u);
    }
  }
//  cout<<u<<" "<<ret<<endl;
  mainres+=(n-ret)*ret;
  return ret;
}

long long solve2(){
  for(long long i=0;i<n;i++){
    mp[all[i]]=i;
  }
  for(long long i=0;i<n;i++){
    if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
      ds1.con(mp[make_pair(all[i].first,all[i].second+1)],i);
    }
    if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
      ds2.con(mp[make_pair(all[i].first+1,all[i].second)],i);
    }
  }
  for(long long i=0;i<n;i++){
    if(mp.count(make_pair(all[i].first,all[i].second+1))!=0){
      long long u=ds2.root(i);
      long long v=ds2.root(mp[make_pair(all[i].first,all[i].second+1)]);
      adja[u].push_back(v);
      adja[v].push_back(u);
    }
    if(mp.count(make_pair(all[i].first+1,all[i].second))!=0){
      long long u=ds1.root(i);
      long long v=ds1.root(mp[make_pair(all[i].first+1,all[i].second)]);
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  }
  dfs(ds1.root(0));
  for(long long i=0;i<n;i++){
    vis[i]=0;
    swap(ds1.sz[i],ds2.sz[i]);
    swap(adj[i],adja[i]);
  }
  dfs(ds2.root(0));
  mainres%=mod;
  return mainres;
}

int DistanceSum(int N,int *X,int *Y){
  n=N;
  for(long long i=0;i<n;i++){
    all.push_back(make_pair(X[i],Y[i]));
  }
  return solve2();
}

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