CSES - HIIT Open 2016 - Results
Submission details
Task:Ethernet cable
Sender:Team Purkka
Submission time:2016-05-28 14:40:55 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.49 sdetails

Compiler report

input/code.cpp: In function 'void test()':
input/code.cpp:129:8: warning: variable 'vi' set but not used [-Wunused-but-set-variable]
   bool vi[50000];
        ^
input/code.cpp:136:7: warning: unused variable 'vic' [-Wunused-variable]
   int vic=0;
       ^

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int pos(int x,int y,int z,int w){ // 0<=x<50, 0<=y<50, 0<=z<5, 0<=w<4
  return w*12500+z*2500+y*50+x;
}
void debug(int po){
  int w=po/12500;
  int z=po/2500%5;
  int y=po/50%50;
  int x=po%50;
  cout<<x<<","<<y<<" z="<<z<<" corner "<<w<<endl;
}
int wall(int x,int y,const string &w){
  if(w=="west")return pos(x-1,y-1,0,2);  // 0 = west  = -x
  if(w=="east")return pos(x,y-1,0,3);    // 1 = east  = +x
  if(w=="north")return pos(x-1,y-1,0,2); // 2 = north = -y
  return pos(x-1,y,0,1);                 // 3 = south = +y
}
// 0 = -x -y
// 1 = +x -y
// 2 = +x +y
// 3 = -x +y
void test(){
  int w,h;
  cin>>w>>h;
  int sx,sy,ex,ey,sp,ep;
  string ws;
  cin>>sx>>sy>>ws;
  sp=wall(sx,sy,ws);
  cin>>ex>>ey>>ws;
  ep=wall(ex,ey,ws);
  
  char r[2*h+1][2*w+1];
  for(int y=0;y<2*h+1;y++){
    for(int x=0;x<2*w+1;x++)cin>>r[y][x];
  }
  vector<pair<int,int>> co[50000];
  for(int x=0;x<w;x++){
    for(int y=0;y<h;y++){
      char wl=r[2*y+1][2*x],wr=r[2*y+1][2*x+2],wu=r[2*y][2*x+1],wd=r[2*y+2][2*x+1];
      // ----------------- JOHDOT VAAKASUORAAN KATOSSA ---------------
      co[pos(x,y,3,0)].push_back({pos(x,y,3,1),1});
      co[pos(x,y,3,0)].push_back({pos(x,y,3,3),1});
      co[pos(x,y,3,1)].push_back({pos(x,y,3,2),1});
      co[pos(x,y,3,1)].push_back({pos(x,y,3,0),1});
      co[pos(x,y,3,2)].push_back({pos(x,y,3,3),1});
      co[pos(x,y,3,2)].push_back({pos(x,y,3,1),1});
      co[pos(x,y,3,3)].push_back({pos(x,y,3,0),1});
      co[pos(x,y,3,3)].push_back({pos(x,y,3,2),1});
      // ---------------- JOHDOT EI-SEINÄRAJOJEN YLI ------------------
      for(int z=0;z<=3;z++){
	if(x>0&&wl=='.'){ // ei seinää vasemmalla ja ei vasen reuna
	  co[pos(x,y,z,0)].push_back({pos(x-1,y,z,1),0});
	  co[pos(x,y,z,3)].push_back({pos(x-1,y,z,2),0});
	}
	if(x<w-1&&wr=='.'){ // ei seinää oikealla ja ei oikea reuna
	  co[pos(x,y,z,1)].push_back({pos(x+1,y,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x+1,y,z,3),0});
	}
	if(y>0&&wu=='.'){ // ei seinää ylhäällä ja ei yläreuna
	  co[pos(x,y,z,0)].push_back({pos(x,y-1,z,3),0});
	  co[pos(x,y,z,1)].push_back({pos(x,y-1,z,2),0});
	}
	if(y<h-1&&wd=='.'){ // ei seinää alhaalla ja ei alareuna
	  co[pos(x,y,z,3)].push_back({pos(x,y+1,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x,y+1,z,1),0});
	}
      }
      for(int z=0;z<=2;z++){
	// ------------- JOHDOT OVISTA ---------------
	if(x>0&&wl=='D'){ // ovi vasemmalla ja ei vasen reuna
	  co[pos(x,y,z,0)].push_back({pos(x-1,y,z,1),0});
	  co[pos(x,y,z,3)].push_back({pos(x-1,y,z,2),0});
	}
	if(x<w-1&&wr=='D'){ // ovi oikealla ja ei oikea reuna
	  co[pos(x,y,z,1)].push_back({pos(x+1,y,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x+1,y,z,3),0});
	}
	if(y>0&&wu=='D'){ // ovi ylhäällä ja ei yläreuna
	  co[pos(x,y,z,0)].push_back({pos(x,y-1,z,3),0});
	  co[pos(x,y,z,1)].push_back({pos(x,y-1,z,2),0});
	}
	if(y<h-1&&wd=='D'){ // ovi alhaalla ja ei alareuna
	  co[pos(x,y,z,3)].push_back({pos(x,y+1,z,0),0});
	  co[pos(x,y,z,2)].push_back({pos(x,y+1,z,1),0});
	}
	// ------------ JOHDOT PYSTYSUORAAN ----------------
	if(wl=='|'||wu=='-'||wl=='D'||wu=='D'){ // seinä tai ovi ylhäällä tai vasemmalla
	  co[pos(x,y,z,0)].push_back({pos(x,y,z+1,0),1});
	  co[pos(x,y,z+1,0)].push_back({pos(x,y,z,0),1});
	}
	if(wr=='|'||wu=='-'||wr=='D'||wu=='D'){ // seinä tai ovi ylhäällä tai oikealla
	  co[pos(x,y,z,1)].push_back({pos(x,y,z+1,1),1});
	  co[pos(x,y,z+1,1)].push_back({pos(x,y,z,1),1});
	}
	if(wr=='|'||wd=='-'||wr=='D'||wd=='D'){ // seinä tai ovi alhaalla tai oikealla
	  co[pos(x,y,z,2)].push_back({pos(x,y,z+1,2),1});
	  co[pos(x,y,z+1,2)].push_back({pos(x,y,z,2),1});
	}
	if(wl=='|'||wd=='-'||wl=='D'||wd=='D'){ // seinä tai ovi alhaalla tai vasemmalla
	  co[pos(x,y,z,3)].push_back({pos(x,y,z+1,3),1});
	  co[pos(x,y,z+1,3)].push_back({pos(x,y,z,3),1});
	}
	// ------------ JOHDOT VAAKASUORAAN SEINILLÄ ----------------
	if(wl=='|'){ // seinä vasemmalla
	  co[pos(x,y,z,0)].push_back({pos(x,y,z,3),1});
	  co[pos(x,y,z,3)].push_back({pos(x,y,z,0),1});
	}
	if(wr=='|'){ // seinä oikealla
	  co[pos(x,y,z,1)].push_back({pos(x,y,z,2),1});
	  co[pos(x,y,z,2)].push_back({pos(x,y,z,1),1});
	}
	if(wu=='-'){ // seinä ylhäällä
	  co[pos(x,y,z,0)].push_back({pos(x,y,z,1),1});
	  co[pos(x,y,z,1)].push_back({pos(x,y,z,0),1});
	}
	if(wd=='-'){ // seinä alhaalla
	  co[pos(x,y,z,3)].push_back({pos(x,y,z,2),1});
	  co[pos(x,y,z,2)].push_back({pos(x,y,z,3),1});
	}
      }
    }
  }
  priority_queue<pair<int,int>> qu;
  int v[50000];
  bool vi[50000];
  for(int i=0;i<50000;i++){
    v[i]=999999999;
    vi[i]=0;
  }
  v[sp]=0;
  qu.push({0,sp});
  int vic=0;
  while(!qu.empty()){
    pair<int,int> pa=qu.top();
    int d = -pa.first;
    int i = pa.second;
    qu.pop();
    //if (vi[i]) continue;
    vi[i] = true;
    //vic++;
    //debug(i);
    for (pair<int, int> p : co[i]) {
	int a = p.first;
	int b = p.second;
	if (v[a] > d + b) {
	    v[a] = d + b;
	    qu.push({-v[a], a});
	}
    }
  }
  cout<<v[ep]<<endl;
  //cout<<"reached "<<vic<<" places"<<endl;
  //int s=0;
  //for(int x=0;x<50000;x++)s+=co[x].size();
  //cout<<"done, "<<s<<" connections."<<endl;
}






















int main () {
  int t;
  cin>>t;
  for(int _=0;_<t;_++)test();
}

Test details

Test 1

Verdict:

input
50
7 8
0 6 east
2 3 east
+-+-+-+-+-+-+-+
...

correct output
13
44
67
52
72
...

user output
13
44
69
52
74
...