#pragma region//
#include<bits/stdc++.h>
//#define int long long
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#define f2(i, m) for(int i=0; i<m; i++)
#define f21(i, m) for(int i=1; i<m; i++)
#define f3(i, n, m) for(int i=n; i<m; i++)
#define f2_(i, m) for(int i=m; i>-1; i--)
#define f21_(i, m) for(int i=m; i>0; i--)
#define f3_(i, n, m) for(int i=n; i>=m; i--)
#define travG(idx) for(int i : g[idx])
#define travG_(i, idx) for(int i : g[idx])
#define trav(loop) for(int i : loop)
#define trav_(i, loop) for(int i : loop)
#define trav2(loop, idx) for(int i : loop[idx])
#define trav2_(i, loop, idx) for(int i : loop[idx])
#define ll long long
#define bs bitset
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define ve vector<element>
#define ve_ vector<element_>
#define vpii vector<pair<int, int>>
#define qi queue<int>
#define qe queue<element>
#define qpii queue<pair<int, int>>
#define si stack<int>
#define se stack<element>
#define spii stack<pair<int, int>>
#define vb vector<bool>
#define pqi priority_queue<int>
#define pqi_ priority_queue<int, vi, greater<int>>
#define pqpii priority_queue<pair<int, int>>
#define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>>
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define len length()
#define elif else if
#define mod 1000000007
#pragma endregion
#define debug
/*
#ifdef debug
#endif
#ifndef debug
#endif
*/
using namespace std;
using vvpib = vector<vector<pair<int, bool>>>;
using vpib = vector<pair<int, bool>>;
using pib = pair<int, bool>;
int n, m;
signed main()// https://tioj.ck.tp.edu.tw/problems/2363
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
/*
pii input[m];
f2(i, m) cin>>input[i].first>>input[i].second;
int srt=input[0].first, stp=input[1].first;
sort(input, input+m, [](pii a, pii b)
{
return (pii){a.second, a.first%a.second} < (pii){b.second, b.first%b.second};
});*/
auto cmp = [](const pii a, const pii b)
{
return (pii){a.second, a.first%a.second} < (pii){b.second, b.first%b.second};
};
priority_queue<pii, vpii, decltype(cmp)> input(cmp);
int tmp[n], pre=0, pre_=0;
vvpib g(n);
int idx = n;// maintain g.size()
int a, b;
cin>>a>>b;
int srt=a;
input.push({a, b});
cin>>a>>b;
int stp=a;
input.push({a, b});
f2(i, m-2)
{
cin>>a>>b;
input.push({a, b});
}
//for(pii &i : input)
while(!input.empty())
{
pii i = input.top(); input.pop();
if(i.second==pre && i.first%i.second==pre_)
{
g[i.first].pb({tmp[i.first], 0});
#ifndef debug
cout<<i.first<<' '<<tmp[i.first]<<' '<<0<<'\n';
#endif
}
else
{
bool flag=0;
for(int j=i.first%i.second; j<n; j+=i.second, flag=1, idx++)
{
g.pb({{j, 0}});
tmp[j]=idx;
#ifndef debug
cout<<idx<<' '<<j<<' '<<0<<'\n';
#endif
if(flag)
{
g[idx-1].pb({idx, 1}), g[idx].pb({-1+idx, 1});
#ifndef debug
cout<<idx<<' '<<idx-1<<' '<<1<<'\n';
cout<<idx-1<<' '<<idx<<' '<<1<<'\n';
#endif
}
}
g[i.first].pb({tmp[i.first], 0});
#ifndef debug
cout<<i.first<<' '<<tmp[i.first]<<' '<<0<<'\n';
#endif
pre=i.second, pre_=i.first%i.second;
}
}
// 01BFS
// to fix
bool vis[idx] = {0};
deque<pii> dq; dq.pb({srt, 0});
while(!dq.empty())
{
pii now = dq.front(); dq.pop_front();
//cout << '\n' << now.first << ' ';
for(pib &ii : g[now.first])
{int i = ii.first;
//cout<<' '<<i;
if(vis[i]&&i>=n) continue;
vis[i]=1;
if(i==stp)
{
cout << now.second+ii.second;
return 0;
}
if(ii.second) dq.pb({i, now.second+1});
else dq.pf({i, now.second});
}
}
//cout << vis[8];
cout << -1;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |