Robots

input/code.cpp: In function 'int main()':
input/code.cpp:41:29: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
       rt[pj]['U']=MP(j, y[j]-py);
                             ^

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MP make_pair
#define F first
#define S second
using namespace std;
int N;
long long T;

int x[101010];
int y[101010];
char d[101010];

vector<pair<pair<int, int>, int> > xs;
vector<pair<pair<int, int>, int> > ys;

pair<int, int> rt[101010][256];
int urt[101010][256];

long long u[101010];
priority_queue<pair<long long, int> > ac;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  for (int i=0; i<101010; ++i) for (int j=0; j<256; ++j) rt[i][j]=MP(-1, 0);
  cin >> N >> T; ++T;
  for (int i=0; i<N; ++i){
    cin >> x[i] >> y[i] >> d[i];
    xs.push_back(MP(MP(x[i], y[i]), i));
    ys.push_back(MP(MP(y[i], x[i]), i));
  }
  sort(xs.begin(), xs.end());
  sort(ys.begin(), ys.end());
  int px=-1000111222; int py;
  int pj;
  for (int i=0; i<N; ++i){
    int j=xs[i].S;
    if (x[j]==px){
      rt[pj]['U']=MP(j, y[j]-py);
      rt[j]['D']=MP(pj, y[j]-py);
    }px=x[j];py=y[j];
    pj=j;
  }
  py=-1000111222;
  for (int i=0; i<N; ++i){
    int j=ys[i].S;
    if (y[j]==py){
      rt[pj]['R']=MP(j, x[j]-px);
      rt[j]['L']=MP(pj, x[j]-px);
    }px=x[j];py=y[j];
    pj=j;
  }
  u[0]=1;
  ac.push(MP(-1, 0));
  while (ac.size()){
    int c0=ac.top().S;
    int dr=d[c0];
    long long t=-ac.top().F;
    if (t!=u[c0]){ac.pop(); continue;}
    ac.pop();
    long long crt=0;
    int w;
    for (int c=c0;rt[c][dr].F!=-1;c=w){
      ++urt[c][dr];
      crt+=rt[c][dr].S;
      w=rt[c][dr].F;
      if (u[w] && u[w]<=u[c0]+crt){
	rt[c][dr].F=-1;
	continue;
      }
      u[w]=u[c0]+crt;
      ac.push(MP(-u[w], w));
      rt[c][dr].F=-1;
    }
  }
  for (int i=0; i<N; ++i){
    long long xi=x[i];
    long long yi=y[i];
    if (u[i] && u[i]<T){
      if (d[i]=='U') yi+=T-u[i];
      if (d[i]=='D') yi-=T-u[i];
      if (d[i]=='L') xi-=T-u[i];
      if (d[i]=='R') xi+=T-u[i];
    }
    cout << xi << " " << yi << "\n";
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED