#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;
int m, n;
vector<int> vertex;
vector<int> dummy[30005];
vector<int> dx[30005];
bool r_dir[30005][180], l_dir[30005][180];
vector<vector<int> > graph0, graph1;
priority_queue<pi,vector<pi>,greater<pi> > pq;
bool vis[11000000];
inline int oldpi(int i, int j){
return n * j + i;
}
inline int oldpi_first(int p){
return (p % n + n) % n;
}
inline int oldpi_second(int p){
return (p - oldpi_first(p)) / n;
}
int dijkstra(int st, int ed){
pq.push(pi(0,st));
while (!pq.empty()) {
pi t = pq.top();
pq.pop();
if(t.second == ed){
return t.first;
}
if(vis[t.second]) continue;
vis[t.second] = 1;
for (auto &i : graph0[t.second]){
if(!vis[i]){
pq.push(pi(t.first,i));
}
};
for (auto &i : graph1[t.second]){
if(!vis[i]){
pq.push(pi(1 + t.first,i));
}
}
}
return -1;
}
int main(){
int st, ed;
scanf("%d %d",&n,&m);
for (int i=0; i<m; i++) {
int x,y;
scanf("%d %d",&x,&y);
if(i == 0){
st = x;
}
else if(i == 1){
ed = x;
}
if(y < 180){
r_dir[x][y] = 1;
l_dir[x][y] = 1;
}
else{
for (int j=0; j * y + x < n; j++) {
dx[j * y + x].push_back(y);
}
for (int j=0; j * y + x >= 0; j--) {
dx[j * y + x].push_back(-y);
}
}
dummy[x].push_back(y);
}
for (int i=1; i<180; i++) {
for (int j=i; j<n; j++) {
r_dir[j][i] |= r_dir[j - i][i];
}
for (int j=n-i-1; j>=0; j--) {
l_dir[j][i] |= l_dir[j + i][i];
}
for (int j=0; j<n; j++) {
if(r_dir[j][i]){
dx[j].push_back(i);
}
if(l_dir[j][i]){
dx[j].push_back(-i);
}
}
}
for (int i=0; i<n; i++) {
sort(dx[i].begin(),dx[i].end());
dx[i].resize(unique(dx[i].begin(),dx[i].end()) - dx[i].begin());
for (auto &j : dx[i]){
printf("%d %d\n",i,j);
vertex.push_back(oldpi(i,j));
}
}
sort(vertex.begin(),vertex.end());
graph0.resize(n + vertex.size());
graph1.resize(n + vertex.size());
for (int i=0; i<n; i++) {
for(auto &j : dummy[i]){
int pos = (int)(lower_bound(vertex.begin(),vertex.end(),oldpi(i,j)) - vertex.begin());
if(pos != vertex.size() && vertex[pos] == oldpi(i,j)){
graph0[i].push_back(pos + n);
}
pos = (int)(lower_bound(vertex.begin(),vertex.end(),oldpi(i,-j)) - vertex.begin());
if(pos != vertex.size() && vertex[pos] == oldpi(i,-j)){
graph0[i].push_back(pos + n);
}
}
}
for (int i=0; i<vertex.size(); i++){
int tmp = vertex[i];
graph0[i+n].push_back(oldpi_first(vertex[i]));
if(oldpi_first(tmp) + oldpi_second(tmp) < 0 || oldpi_first(tmp) + oldpi_second(tmp) >= n)
continue;
tmp = oldpi(oldpi_first(tmp) + oldpi_second(tmp),oldpi_second(tmp));
int np = (int)(lower_bound(vertex.begin(),vertex.end(),tmp) - vertex.begin());
graph0[i+n].push_back(oldpi_first(vertex[i]));
if(np == vertex.size() || vertex[np] != tmp) continue;
graph1[i+n].push_back(np + n);
}
printf("%d",dijkstra(st,ed));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
24280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
24280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
