Submission #1290317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290317		Faisal_Saqib	Ideal city (IOI12_city)	C++20	100 / 100	206 ms	35516 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+10;
map<ll,set<ll>> mpx;
map<ll,set<ll>> mpy;
map<pair<ll,ll>,ll> nv,nh; // mapping for (x,y) to node in vertical tree and node in horizontal tree
set<ll> ma[N];
ll lh=0,lv=0,w[N],sm[N],mod=1e9,n,ans=0;
void dfs(ll x,ll p=-1)
{
  sm[x]=w[x];
  // cout<<"At "<<x<<' '<<w[x]<<endl;
  for(auto y:ma[x])
  {
    if(y==p)continue;
    dfs(y,x);
    // cout<<"down "<<y<<' '<<sm[y]<<endl;
    ans+=((n-sm[y])*sm[y])%mod;
    ans%=mod;
    sm[x]+=sm[y];
  }
}
int DistanceSum(int N, int x[], int y[])
{
  n=N;
  for(ll i=0;i<n;i++)
  {
    mpx[x[i]].insert(y[i]);
    mpy[y[i]].insert(x[i]);
  }
  for(auto t:mpx)
  {
    ll x=t.first;
    ll lst=-1,ly=-1;
    for(auto y:t.second)
    {
      if(ly==(y-1))
      {
        nh[{x,y}]=lst;
        w[lst]++;
      }
      else{
        nh[{x,y}]=++lh;
        w[lh]++;
        lst=lh;
      }
      ly=y;
      auto it=nh.find({x-1,y});
      if(it!=nh.end())
      {
        ma[it->second].insert(lst);
        ma[lst].insert(it->second);
      }
    }
  }
  dfs(1);
  // cout<<ans<<endl;
  for(ll i=1;i<=n;i++)ma[i].clear(),w[i]=0;
  for(auto t:mpy)
  {
    ll x=t.first;
    ll lst=-1,ly=-1;
    for(auto y:t.second)
    {
      if(ly==(y-1))
      {
        nv[{x,y}]=lst;
        w[lst]++;
      }
      else{
        nv[{x,y}]=++lv;
        w[lv]++;
        lst=lv;
      }
      ly=y;
      auto it=nv.find({x-1,y});
      if(it!=nv.end())
      {
        ma[it->second].insert(lst);
        ma[lst].insert(it->second);
      }
    }
  }
  // for(ll i=1;i<=lv;i++)
  // {
  //   cout<<"node "<<i<<' '<<w[i]<<endl;
  //   for(auto j:ma[i])cout<<j<<' ';
  //   cout<<endl;
  // }
  dfs(1);
  return ans;
}

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