Submission #1237559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237559		pcp	Ideal city (IOI12_city)	C++20	0 / 100	1096 ms	18756 KiB

city

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;

ll MOD =1000000000;

ll maxx = pow(2,31)-1;


bool visited[2500][2500];

bool state[2500][2500];

bool deactivated[2500][2500];

int DistanceSum(int N, int *X, int *Y) {

  memset(visited,0,sizeof visited);
  memset(state, false, sizeof state);
  memset(deactivated, false, sizeof deactivated);

  for (int i = 0; i < N;++i){

    state[X[i]][Y[i]]=true;

  }

  ll c=0;

  for (int i = 0; i < N;++i){

    queue<pair<pair<int,int>,int>> kiwi;
    kiwi.push(
      {{X[i],Y[i]},0}
    );

    memset(visited,0,sizeof visited);


    while (kiwi.size()>0){
      pair<pair<int,int>,int> it = kiwi.front();kiwi.pop() ;

      if (!visited[it.first.first][it.first.second]){
        visited[it.first.first][it.first.second]=true;
        pair<int,int> cords[]={

          {1,0},
          {0,1},
          {0,-1},
          {-1,0}
        };

        for (int j = 0 ; j <4;++j){

          pair<int,int> cord = cords[j];
          pair<int,int> newcords={it.first.first+cord.first,it.first.second+cord.second};

          if (newcords.first>=0 && newcords.second>=0 && newcords.first <=maxx && newcords.second <=maxx){

            if (state[newcords.first][newcords.second] && !visited[newcords.first][newcords.second]){

              kiwi.push({newcords,it.second+1});
              if (!deactivated[newcords.first][newcords.second])c+=it.second+1;

              c = c % MOD;
              

            }

          }

        }

      }

      deactivated[X[i]][Y[i]]=true;


    }



  }

  return c;



}

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