#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=3e4+5,BLOCK=305;
const ll inf=2e18;
int n,m,b[maxN+1],p[maxN+1];
ll d[maxN+1][BLOCK+1];
bool vis[maxN+1],ck[maxN+1];
struct duongdi
{
int u,power;
ll w;
bool operator < (const duongdi &o)const
{
return w>o.w;
}
};
vector<duongdi> adj[maxN+1];
priority_queue<duongdi> pq;
vector<int> vec[maxN+1];
void CO(int u,int v,int pw,int power,int w)
{
if(d[v][pw]>d[u][power]+w)
{
d[v][pw]=d[u][power]+w;
pq.push({v,pw,d[v][pw]});
}
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
memset(vis,false,sizeof(vis));
for(int i=0;i<m;i++)
{
cin>>b[i]>>p[i];
if(p[i]<=BLOCK)
{
vec[b[i]].push_back(p[i]);
ck[b[i]]=true;
}
else vis[b[i]]=true;
}
for(int i=0;i<m;i++)
{
if(p[i]<=BLOCK)
{
continue;
}
bool ok=false;
for(int j=b[i]+p[i];j<n;j+=p[i])
{
if(vis[j]||(ck[j]&&!ok))
{
adj[b[i]].push_back({j,0,(j-b[i])/p[i]});
if(ck[j])
{
ok=true;
}
}
}
ok=false;
for(int j=b[i]-p[i];j>=0;j-=p[i])
{
if(vis[j]||(ck[j]&&!ok))
{
adj[b[i]].push_back({j,0,(b[i]-j)/p[i]});
if(ck[j])
{
ok=true;
}
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<=BLOCK;j++)
{
d[i][j]=inf;
}
}
if(p[0]<=BLOCK)
{
d[b[0]][p[0]]=0;
pq.push({b[0],p[0],0});
}
else
{
d[b[0]][0]=0;
pq.push({b[0],0,0});
}
while(!pq.empty())
{
duongdi tmp=pq.top();
pq.pop();
int u=tmp.u,power=tmp.power;
ll w=tmp.w;
//cout<<u<<" "<<power<<" "<<w<<'\n';
if(u==b[1])
{
cout<<d[u][power];
return 0;
}
if(d[u][power]<w)
{
continue;
}
if(power>0)
{
if(u+power<n)
{
CO(u,u+power,power,power,1);
}
if(u-power>=0)
{
CO(u,u-power,power,power,1);
}
if(vis[u])
{
CO(u,u,0,power,0);
}
}
else
{
for(auto i:adj[u])
{
CO(u,i.u,0,power,i.w);
}
}
for(auto i:vec[u])
{
CO(u,u,i,power,0);
}
}
cout<<-1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Correct |
1 ms |
1880 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
1 ms |
1884 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
2 ms |
1884 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1880 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
1 ms |
2140 KB |
Output is correct |
11 |
Correct |
1 ms |
2140 KB |
Output is correct |
12 |
Correct |
1 ms |
2140 KB |
Output is correct |
13 |
Correct |
1 ms |
2140 KB |
Output is correct |
14 |
Correct |
2 ms |
2140 KB |
Output is correct |
15 |
Correct |
1 ms |
2140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1932 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
1 ms |
1884 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1872 KB |
Output is correct |
10 |
Correct |
1 ms |
2140 KB |
Output is correct |
11 |
Correct |
1 ms |
2140 KB |
Output is correct |
12 |
Correct |
1 ms |
2140 KB |
Output is correct |
13 |
Correct |
1 ms |
2140 KB |
Output is correct |
14 |
Correct |
2 ms |
2140 KB |
Output is correct |
15 |
Correct |
2 ms |
2140 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
2 ms |
3676 KB |
Output is correct |
18 |
Correct |
2 ms |
5980 KB |
Output is correct |
19 |
Correct |
3 ms |
6492 KB |
Output is correct |
20 |
Correct |
3 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
2 ms |
5980 KB |
Output is correct |
23 |
Correct |
3 ms |
5724 KB |
Output is correct |
24 |
Correct |
3 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6748 KB |
Output is correct |
26 |
Correct |
3 ms |
6748 KB |
Output is correct |
27 |
Correct |
3 ms |
6748 KB |
Output is correct |
28 |
Correct |
4 ms |
6780 KB |
Output is correct |
29 |
Correct |
6 ms |
7000 KB |
Output is correct |
30 |
Correct |
3 ms |
6492 KB |
Output is correct |
31 |
Correct |
6 ms |
6492 KB |
Output is correct |
32 |
Correct |
5 ms |
6488 KB |
Output is correct |
33 |
Correct |
8 ms |
6744 KB |
Output is correct |
34 |
Correct |
6 ms |
6744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1884 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1880 KB |
Output is correct |
5 |
Correct |
1 ms |
1884 KB |
Output is correct |
6 |
Correct |
1 ms |
2136 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
1 ms |
1884 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
1 ms |
2140 KB |
Output is correct |
11 |
Correct |
1 ms |
2140 KB |
Output is correct |
12 |
Correct |
1 ms |
2140 KB |
Output is correct |
13 |
Correct |
1 ms |
2140 KB |
Output is correct |
14 |
Correct |
2 ms |
2140 KB |
Output is correct |
15 |
Correct |
2 ms |
2140 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
2 ms |
3676 KB |
Output is correct |
18 |
Correct |
3 ms |
5980 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
3 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
2 ms |
5980 KB |
Output is correct |
23 |
Correct |
2 ms |
5724 KB |
Output is correct |
24 |
Correct |
3 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6748 KB |
Output is correct |
26 |
Correct |
3 ms |
6744 KB |
Output is correct |
27 |
Correct |
3 ms |
6748 KB |
Output is correct |
28 |
Correct |
3 ms |
6748 KB |
Output is correct |
29 |
Correct |
5 ms |
6748 KB |
Output is correct |
30 |
Correct |
3 ms |
6492 KB |
Output is correct |
31 |
Correct |
4 ms |
6748 KB |
Output is correct |
32 |
Correct |
3 ms |
6492 KB |
Output is correct |
33 |
Correct |
9 ms |
6812 KB |
Output is correct |
34 |
Correct |
6 ms |
6748 KB |
Output is correct |
35 |
Correct |
7 ms |
6236 KB |
Output is correct |
36 |
Correct |
2 ms |
4540 KB |
Output is correct |
37 |
Correct |
7 ms |
8024 KB |
Output is correct |
38 |
Correct |
8 ms |
8280 KB |
Output is correct |
39 |
Correct |
7 ms |
8028 KB |
Output is correct |
40 |
Correct |
7 ms |
8028 KB |
Output is correct |
41 |
Correct |
8 ms |
8340 KB |
Output is correct |
42 |
Correct |
5 ms |
7192 KB |
Output is correct |
43 |
Correct |
5 ms |
7316 KB |
Output is correct |
44 |
Correct |
5 ms |
7344 KB |
Output is correct |
45 |
Correct |
51 ms |
7892 KB |
Output is correct |
46 |
Correct |
39 ms |
7892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1880 KB |
Output is correct |
2 |
Correct |
1 ms |
1884 KB |
Output is correct |
3 |
Correct |
1 ms |
1884 KB |
Output is correct |
4 |
Correct |
1 ms |
1884 KB |
Output is correct |
5 |
Correct |
1 ms |
1884 KB |
Output is correct |
6 |
Correct |
1 ms |
1884 KB |
Output is correct |
7 |
Correct |
1 ms |
1884 KB |
Output is correct |
8 |
Correct |
2 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1884 KB |
Output is correct |
10 |
Correct |
1 ms |
2140 KB |
Output is correct |
11 |
Correct |
1 ms |
2140 KB |
Output is correct |
12 |
Correct |
1 ms |
2140 KB |
Output is correct |
13 |
Correct |
1 ms |
2140 KB |
Output is correct |
14 |
Correct |
1 ms |
2140 KB |
Output is correct |
15 |
Correct |
1 ms |
2140 KB |
Output is correct |
16 |
Correct |
1 ms |
2396 KB |
Output is correct |
17 |
Correct |
2 ms |
3676 KB |
Output is correct |
18 |
Correct |
3 ms |
5976 KB |
Output is correct |
19 |
Correct |
3 ms |
6492 KB |
Output is correct |
20 |
Correct |
3 ms |
6560 KB |
Output is correct |
21 |
Correct |
1 ms |
2652 KB |
Output is correct |
22 |
Correct |
2 ms |
5980 KB |
Output is correct |
23 |
Correct |
3 ms |
5784 KB |
Output is correct |
24 |
Correct |
3 ms |
6492 KB |
Output is correct |
25 |
Correct |
3 ms |
6748 KB |
Output is correct |
26 |
Correct |
3 ms |
6748 KB |
Output is correct |
27 |
Correct |
3 ms |
6748 KB |
Output is correct |
28 |
Correct |
4 ms |
6744 KB |
Output is correct |
29 |
Correct |
5 ms |
6748 KB |
Output is correct |
30 |
Correct |
3 ms |
6492 KB |
Output is correct |
31 |
Correct |
4 ms |
6492 KB |
Output is correct |
32 |
Correct |
5 ms |
6492 KB |
Output is correct |
33 |
Correct |
8 ms |
6908 KB |
Output is correct |
34 |
Correct |
6 ms |
6748 KB |
Output is correct |
35 |
Correct |
7 ms |
6236 KB |
Output is correct |
36 |
Correct |
2 ms |
4444 KB |
Output is correct |
37 |
Correct |
7 ms |
8028 KB |
Output is correct |
38 |
Correct |
8 ms |
8260 KB |
Output is correct |
39 |
Correct |
7 ms |
8028 KB |
Output is correct |
40 |
Correct |
7 ms |
8024 KB |
Output is correct |
41 |
Correct |
8 ms |
8284 KB |
Output is correct |
42 |
Correct |
5 ms |
7260 KB |
Output is correct |
43 |
Correct |
5 ms |
7272 KB |
Output is correct |
44 |
Correct |
5 ms |
7260 KB |
Output is correct |
45 |
Correct |
52 ms |
7804 KB |
Output is correct |
46 |
Correct |
38 ms |
7896 KB |
Output is correct |
47 |
Correct |
23 ms |
37072 KB |
Output is correct |
48 |
Correct |
29 ms |
58972 KB |
Output is correct |
49 |
Correct |
29 ms |
63832 KB |
Output is correct |
50 |
Correct |
34 ms |
69460 KB |
Output is correct |
51 |
Correct |
37 ms |
76368 KB |
Output is correct |
52 |
Correct |
39 ms |
76368 KB |
Output is correct |
53 |
Correct |
38 ms |
74328 KB |
Output is correct |
54 |
Correct |
29 ms |
73564 KB |
Output is correct |
55 |
Correct |
29 ms |
73556 KB |
Output is correct |
56 |
Correct |
36 ms |
75100 KB |
Output is correct |
57 |
Correct |
31 ms |
73808 KB |
Output is correct |
58 |
Correct |
39 ms |
74324 KB |
Output is correct |
59 |
Correct |
35 ms |
74324 KB |
Output is correct |
60 |
Correct |
34 ms |
74324 KB |
Output is correct |
61 |
Correct |
33 ms |
74232 KB |
Output is correct |
62 |
Correct |
72 ms |
77912 KB |
Output is correct |
63 |
Correct |
96 ms |
74580 KB |
Output is correct |
64 |
Correct |
139 ms |
74576 KB |
Output is correct |
65 |
Correct |
359 ms |
74772 KB |
Output is correct |
66 |
Correct |
534 ms |
74904 KB |
Output is correct |
67 |
Correct |
304 ms |
74960 KB |
Output is correct |