Submission #1195079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195079		nikulid	이상적인 도시 (IOI12_city)	C++20	32 / 100	250 ms	327680 KiB

city

#include <climits>
#include <vector>
#include <queue>


using namespace std;


/*

  lemma: I will solve subtasks 1 and 2
  proof:

*/

queue<vector<int>> q;

long long ans=0;
vector<vector<int>> visitted, exists; // both are [y][x]
vector<vector<bool>> DONE;
void bfs(int I, int x, int y, int curdist, int ox, int oy){
  //cout<<"bfs called..\n";
  visitted[y][x]=I;
  ans %= 1000000000;
  vector<int> nxt(6);
  curdist++;
  //cout<<I<<": visitting ["<<y<<","<<x<<"] with distance "<<curdist<<"\n";
  
  nxt[0]=I;
  nxt[3]=curdist;
  nxt[4]=ox;
  nxt[5]=oy;
  
  // coords is [x,y]

  // UP
  if(exists[y+1][x] && visitted[y+1][x] != I){
    if(exists[y+1][x] > exists[oy][ox]){
      ans += curdist;
      //bfs(I, x+1, y+1, curdist, oy, ox);
    }
    nxt[1]=x;
    nxt[2]=y+1;
    visitted[y+1][x]=I;
    q.push(nxt);
  }
  
  // LEFT
  if(exists[y][x-1] && visitted[y][x-1] != I){
    if(exists[y][x-1] > exists[oy][ox]){
      ans += curdist;
      //bfs(I, x-1, y, curdist, oy, ox);
    }
    nxt[1]=x-1;
    nxt[2]=y;
    visitted[y][x-1]=I;
    q.push(nxt);
  }
  
  // DOWN
  if(exists[y-1][x] && visitted[y-1][x] != I){
    //cout<<"3rd check outer alert\n";
    if(exists[y-1][x] > exists[oy][ox]){
      //cout<<"3rd check inner alert\n";
      ans += curdist;
      //bfs(I, x, y-1, curdist, oy, ox);
    }
    nxt[1]=x;
    nxt[2]=y-1;
    visitted[y-1][x]=I;
    q.push(nxt);
  } else{
    //cout<<"\tno down.\n";
  }
  

  // RIGHT
  if(exists[y][x+1] && visitted[y][x+1] != I){
    if(exists[y][x+1] > exists[oy][ox]){
      ans += curdist;
      //bfs(I, x+1, y, curdist, oy, ox);
    }
    nxt[1]=x+1;
    nxt[2]=y;
    visitted[y][x+1]=I;
    q.push(nxt);
  }
  //cout<<"returning..\n";
  return;
}

int DistanceSum(int N, int *X, int *Y) {
  DONE = vector<vector<bool>>(N+5, vector<bool>(N+5, 0));
  visitted = vector<vector<int>>(N+5, vector<int>(N+5, 0));
  exists = vector<vector<int>>(N+5, vector<int>(N+5, 0));

  // find min X and Y values, to translate the graph to start at (1,1)
  int minX=INT_MAX-1, minY=INT_MAX-1;
  for(int i=0; i<N; i++){
    minX = min(minX, X[i]);
    minY = min(minY, Y[i]);
  }
  //cout<<"translating each coordinate "<<minX-1<<" to the left and "<<minY-1<<" down !\n";
  for(int i=0; i<N; i++){
    exists[Y[i]-minY+1][X[i]-minX+1] = i+1;
  }
  vector<int> cur;

  for(int y=0; y<N; y++){
    //cout<<"\n";
    for(int x=0; x<N; x++){
      //cout<<(exists[y][x] ? "#" : ".");
    }
  }
  //cout<<"\n";

  for(int i=0; i<N; i++){
    bfs(i+1, X[i]-minX+1, Y[i]-minY+1, 0, X[i]-minX+1, Y[i]-minY+1);
    while(!q.empty()){
      cur = q.front();
      q.pop();
      bfs(cur[0], cur[1], cur[2], cur[3], cur[4], cur[5]);
    }
  }
  ans %= 1000000000;
  return ans;
}

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