oj.uz

Submission #66878

# Submission time Handle Problem Language Result Execution time Memory
66878 2018-08-12T17:47:31 Z Bodo171 Ideal city (IOI12_city) C++14
100 / 100
 234 ms 27848 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2800 KB Output is correct
3 Correct 6 ms 2856 KB Output is correct
4 Correct 4 ms 2856 KB Output is correct
5 Correct 5 ms 2856 KB Output is correct
6 Correct 5 ms 2856 KB Output is correct
7 Correct 4 ms 2856 KB Output is correct
8 Correct 5 ms 2896 KB Output is correct
9 Correct 6 ms 2924 KB Output is correct
10 Correct 4 ms 3092 KB Output is correct
11 Correct 5 ms 3092 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3096 KB Output is correct
2 Correct 6 ms 3104 KB Output is correct
3 Correct 7 ms 3240 KB Output is correct
4 Correct 6 ms 3252 KB Output is correct
5 Correct 7 ms 3392 KB Output is correct
6 Correct 7 ms 3392 KB Output is correct
7 Correct 8 ms 3436 KB Output is correct
8 Correct 7 ms 3436 KB Output is correct
9 Correct 7 ms 3436 KB Output is correct
10 Correct 8 ms 3436 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5020 KB Output is correct
2 Correct 27 ms 5168 KB Output is correct
3 Correct 68 ms 8172 KB Output is correct
4 Correct 66 ms 8608 KB Output is correct
5 Correct 135 ms 13420 KB Output is correct
6 Correct 143 ms 14324 KB Output is correct
7 Correct 155 ms 15316 KB Output is correct
8 Correct 149 ms 15864 KB Output is correct
9 Correct 159 ms 16784 KB Output is correct
10 Correct 210 ms 21672 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 21672 KB Output is correct
2 Correct 34 ms 21672 KB Output is correct
3 Correct 119 ms 21672 KB Output is correct
4 Correct 127 ms 21672 KB Output is correct
5 Correct 234 ms 26120 KB Output is correct
6 Correct 189 ms 26120 KB Output is correct
7 Correct 228 ms 27848 KB Output is correct
8 Correct 213 ms 27848 KB Output is correct
9 Correct 157 ms 27848 KB Output is correct
10 Correct 171 ms 27848 KB Output is correct