Submission #66878

#	Time	Username	Problem	Language	Result	Execution time	Memory
66878		Bodo171	Ideal city (IOI12_city)	C++14	100 / 100	234 ms	27848 KiB

city

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define x first
#define y second
using namespace std;
const int nmax=100005;
long long mod=1000*1000*1000;
map< pair<int,int>,int > m,much;
pair<int,int> v[nmax];
pair<int,int> el,pp;
vector<int> ad[nmax];
long long en;
int i,compo,j,n,a,b,cc;
int xcord[nmax],ystart[nmax],len[nmax],c[nmax];
long long w[nmax];
long long sum;
void dfs(int x)
{
    w[x]=len[x];
    for(int i=0;i<ad[x].size();i++)
        if(!w[ad[x][i]])
    {
        dfs(ad[x][i]);
        w[x]+=w[ad[x][i]];
    }
    sum+=1LL*(en-w[x])*w[x];
}
long long solve(int N,int *X,int *Y)
{
     en=n=N;
  for(int i=0;i<N;i++)
    {
        v[i+1].x=X[i];
        v[i+1].y=Y[i];
    }
  sort(v+1,v+N+1);
  for(i=1;i<=N;i++)
  {
          m[v[i]]=i;
          compo++;
          xcord[compo]=v[i].x;
          ystart[compo]=v[i].y;
          len[compo]=0;
          j=i;
          while(j<=N&&v[j].x==v[i].x&&v[j].y==ystart[compo]+len[compo])
            c[j]=compo,j++,len[compo]++;
          j--;
      i=j;
  }
  for(i=1;i<=N;i++)
    m[v[i]]=i;
  for(i=1;i<=compo;i++)
  {
      a=xcord[i];b=ystart[i];
      for(b=ystart[i];b<ystart[i]+len[i];b++)
      {
          el={a-1,b};
          if(m[el])
            {
                cc=c[m[el]];
                pp={i,cc};
                if(!much[pp])
                    {
                        ad[i].push_back(cc);
                        ad[cc].push_back(i);
                        much[pp]=1;
                    }
            }
      }
  }
  sum=0;
  dfs(1);
  for(i=1;i<=compo;i++)
    ad[i].clear(),w[i]=0;
  m.clear();much.clear();compo=0;
  return sum;
}
int DistanceSum(int N, int *X, int *Y) {
  long long ret= 1LL*((solve(N,X,Y)+solve(N,Y,X)))%mod;
  return ret;
}

Compilation message (stderr)

city.cpp: In function 'void dfs(int)':
city.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~

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