Code Submission Evaluation System Login

HIIT Open 2016

Start:2016-05-28 11:00:00
End:2016-05-28 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2016 - Results
History
2016-05-28 15:35:01
2016-05-28 15:31:15
2016-05-28 15:00:42
2016-05-28 14:40:55
Task:Ethernet cable
Sender:Team Purkka
Submission time:2016-05-28 15:35:01
Language:C++
Status:READY
Result:WRONG ANSWER

Test results

testverdicttime (s)
#1WRONG ANSWER0.71 / 2.00details

Compiler report

input/code.cpp: In function 'void test()':
input/code.cpp:171:8: warning: variable 'vi' set but not used [-Wunused-but-set-variable]
   bool vi[50000];
        ^

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;
}
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
}
inline bool walk(char t){
  return t=='D'||t=='.';
}
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});
	}
	// ---------------- JOHDOT KULMIEN YMPÄRI -----------------
	if(x>0&&y>0){
	  if((wu=='.'&&r[2*y-1][2*x]=='.')||(wl=='.'&&r[2*y][2*x-1]=='.')){
	    co[pos(x,y,z,0)].push_back({pos(x-1,y-1,z,2),0});
	    co[pos(x-1,y-1,z,2)].push_back({pos(x,y,z,0),0});
	  }
	}
	if(x<w-1&&y>0){
	  if((wu=='.'&&r[2*y-1][2*x+2]=='.')||(wr=='.'&&r[2*y][2*x+3]=='.')){
	    co[pos(x,y,z,1)].push_back({pos(x+1,y-1,z,3),0});
	    co[pos(x+1,y-1,z,3)].push_back({pos(x,y,z,1),0});
	  }
	}
	if(x<w-1&&y<h-1){
	  if((wd=='.'&&r[2*y+3][2*x+2]=='.')||(wr=='.'&&r[2*y+2][2*x+3]=='.')){
	    co[pos(x,y,z,2)].push_back({pos(x+1,y+1,z,0),0});
	    co[pos(x+1,y+1,z,0)].push_back({pos(x,y,z,2),0});
	  }
	}
	if(x>0&&y<h-1){
	  if((wd=='.'&&r[2*y+3][2*x]=='.')||(wl=='.'&&r[2*y+2][2*x-1]=='.')){
	    co[pos(x,y,z,3)].push_back({pos(x-1,y+1,z,1),0});
	    co[pos(x-1,y+1,z,1)].push_back({pos(x,y,z,3),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 KULMIEN YMPÄRI OVISTA -----------------
	if(x>0&&y>0){
	  if((walk(wu)&&walk(r[2*y-1][2*x]))||(walk(wl)&&walk(r[2*y][2*x-1]))){
	    co[pos(x,y,z,0)].push_back({pos(x-1,y-1,z,2),0});
	    co[pos(x-1,y-1,z,2)].push_back({pos(x,y,z,0),0});
	  }
	}
	if(x<w-1&&y>0){
	  if((walk(wu)&&walk(r[2*y-1][2*x+2]))||(walk(wr)&&walk(r[2*y][2*x+3]))){
	    co[pos(x,y,z,1)].push_back({pos(x+1,y-1,z,3),0});
	    co[pos(x+1,y-1,z,3)].push_back({pos(x,y,z,1),0});
	  }
	}
	if(x<w-1&&y<h-1){
	  if((walk(wd)&&walk(r[2*y+3][2*x+2]))||(walk(wr)&&walk(r[2*y+2][2*x+3]))){
	    co[pos(x,y,z,2)].push_back({pos(x+1,y+1,z,0),0});
	    co[pos(x+1,y+1,z,0)].push_back({pos(x,y,z,2),0});
	  }
	}
	if(x>0&&y<h-1){
	  if((walk(wd)&&walk(r[2*y+3][2*x]))||(walk(wl)&&walk(r[2*y+2][2*x-1]))){
	    co[pos(x,y,z,3)].push_back({pos(x-1,y+1,z,1),0});
	    co[pos(x-1,y+1,z,1)].push_back({pos(x,y,z,3),0});
	  }
	}
	// ------------ JOHDOT PYSTYSUORAAN ----------------
	if(walk(wl)||walk(wu)){ // 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(walk(wr)||walk(wu)){ // 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(walk(wr)||walk(wd)){ // 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(walk(wl)||walk(wd)){ // 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;
}






















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 main () {
  int t;
  cin>>t;
  for(int _=0;_<t;_++)test();
}

Test details

Test 1

Verdict: WRONG ANSWER

input
50
7 8
0 6 east
2 3 east
+-+-+-+-+-+-+-+
|...|.........|
+.+.+.+.+.+.+.+
|...|.........|
+.+.+.+.+.+.+.+
|...|.........|
+.+.+.+.+.+.+.+
|...|.........|
+.+.+-+D+-+-+-+
|.............|
+.+.+.+.+.+.+.+
|.............|
+.+.+.+.+.+.+.+
|.............|
+.+.+.+.+.+.+.+
|.............|
...
view   save

correct output
13
44
67
52
72
30
30
33
34
25
29
13
49
59
60
79
43
75
27
89
...
view   save

user output
13
44
69
52
74
30
32
37
38
25
29
15
49
59
62
81
43
75
27
91
...
view   save