#include <bits/stdc++.h>
#define N 30005
using namespace std;
vector<int> v[N];
bool vis[N];
map<pair<int,int>,set<pair<int,int>>> mp;
set<pair<int,int>> extend;
int n;
void add(pair<int,int> a,pair<int,int> b){
//cout << a.first << " " << a.second << " " << b.first << " " << b.second << endl;
if(mp[a].size() && mp[a].lower_bound({b.second+a.first + 1,0}) != mp[a].begin()){
auto c = *prev(mp[a].lower_bound({b.second+a.first + 1,0}));
if(c.second >= a.first - 1){
b.first = min(b.first,c.first);
b.second = max(b.second,c.second);
mp[a].erase(c);
}
}
if(mp[a].size() && mp[a].lower_bound({b.first,0}) != mp[a].begin()){
auto c = *prev(mp[a].lower_bound({b.first,0}));
if(c.second >= a.first - 1){
b.first = min(b.first,c.first);
b.second = max(b.second,c.second);
mp[a].erase(c);
}
}
//cout << b.first << " " << b.second << endl;
mp[a].insert(b);
if(extend.find(a) != extend.end())
extend.erase(a);
if(mp[a].size() > 1)
extend.insert(a);
int l = mp[a].begin()->first;
int r = mp[a].rbegin()->second;
if(l - a.first >= 0 || r + a.first < n)
extend.insert(a);
}
void solve(){
int m;
cin >> n >> m;
int st = -1;
for(int i=1;i<=m;i++){
int a,b;
cin >> a >> b;
if(st == -1)st = a;
v[a].push_back(b);
}
vector<int> nws;
vis[st] = 1;
nws.push_back(st);
int cnt = 0;
while(nws.size() || extend.size()){
vector<int> nxt;
for(auto u:nws){
if(u == 1){
cout << cnt << endl;
return;
}
//cout << u << endl;
for(auto c:v[u]){
add({c,u % c},{u,u});
}
}
vector<pair<int,int>> tmp;
for(auto u:extend){
//cout << u.first << " " << u.second << endl;
tmp.push_back(u);
}
for(auto u:tmp){
vector<pair<int,int>> tmp2;
for(auto c:mp[u]){
if(c.first - u.first >= 0)
tmp2.push_back({c.first - u.first,c.first - u.first});
if(c.second + u.first < n)
tmp2.push_back({c.second + u.first,c.second + u.first});
}
for(auto c:tmp2){
if(!vis[c.first]){
vis[c.first] = 1;
nxt.push_back(c.first);
}
add(u,c);
}
}
swap(nws,nxt);
cnt++;
}
cout << -1 << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
