提出 #70875832

ソースコード 拡げる

#include<iostream>
#include<queue>
using namespace std;

const int N=1e5+5;

int n;

namespace graph{
	
	#define rep for(int i=head[u];~i;i=e[i].nxt)
	#define handle int v=e[i].v,w=e[i].w;
	
	int idx=-1;
	
	int head[N];
	
	struct edge{
		int v,nxt,w;
	}e[N<<3];
	
	inline void add(int u,int v,int w){
		return e[++idx]={v,head[u],w},head[u]=idx,void();
	}
	
	int dis[N];
	bool vis[N];
	
	inline void SPFA(int s){
		for(int i=0;i<N;++i)dis[i]=1e9;
		queue<int>q;q.push(s),dis[s]=1;
		while(!q.empty()){
			int u=q.front();q.pop(),vis[u]=0;
			rep{
				handle;
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					if(!vis[v])vis[v]=1,q.push(v);
				}
			}
		}
		return ;
	}
	
	#undef rep
	#undef handle
	
}using namespace graph;

signed main(){
	for(int i=0;i<N;++i)head[i]=-1;
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	for(int i=0;i<n;++i)add(i,(i*10)%n,0),add(i,(i+1)%n,1);
	return SPFA(1),cout<<dis[0]<<"\n",0;
}

提出情報

提出日時
問題 D - Small Multiple
ユーザ DX3906_ourstar
言語 C++ 20 (gcc 12.2)
得点 700
コード長 976 Byte
結果 AC
実行時間 15 ms
メモリ 6928 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 700 / 700
結果
AC × 3
AC × 67
セット名 テストケース
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt
ケース名 結果 実行時間 メモリ
01.txt AC 1 ms 4196 KiB
02.txt AC 1 ms 4200 KiB
03.txt AC 1 ms 4376 KiB
04.txt AC 1 ms 4312 KiB
05.txt AC 1 ms 4224 KiB
06.txt AC 1 ms 4260 KiB
07.txt AC 1 ms 4196 KiB
08.txt AC 1 ms 4376 KiB
09.txt AC 1 ms 4232 KiB
10.txt AC 1 ms 4256 KiB
11.txt AC 1 ms 4252 KiB
12.txt AC 1 ms 4376 KiB
13.txt AC 2 ms 4256 KiB
14.txt AC 1 ms 4204 KiB
15.txt AC 1 ms 4252 KiB
16.txt AC 1 ms 4228 KiB
17.txt AC 2 ms 4256 KiB
18.txt AC 1 ms 4308 KiB
19.txt AC 1 ms 4316 KiB
20.txt AC 1 ms 4256 KiB
21.txt AC 4 ms 6720 KiB
22.txt AC 3 ms 6716 KiB
23.txt AC 11 ms 6816 KiB
24.txt AC 12 ms 6928 KiB
25.txt AC 6 ms 6756 KiB
26.txt AC 10 ms 6700 KiB
27.txt AC 11 ms 6700 KiB
28.txt AC 8 ms 6800 KiB
29.txt AC 10 ms 6820 KiB
30.txt AC 15 ms 6804 KiB
31.txt AC 1 ms 4228 KiB
32.txt AC 1 ms 4256 KiB
33.txt AC 11 ms 6100 KiB
34.txt AC 4 ms 5136 KiB
35.txt AC 8 ms 6040 KiB
36.txt AC 10 ms 6564 KiB
37.txt AC 3 ms 4720 KiB
38.txt AC 3 ms 5276 KiB
39.txt AC 4 ms 5756 KiB
40.txt AC 1 ms 4396 KiB
41.txt AC 5 ms 6588 KiB
42.txt AC 7 ms 6688 KiB
43.txt AC 2 ms 4556 KiB
44.txt AC 1 ms 4324 KiB
45.txt AC 3 ms 5460 KiB
46.txt AC 4 ms 5780 KiB
47.txt AC 1 ms 4292 KiB
48.txt AC 4 ms 6448 KiB
49.txt AC 5 ms 6368 KiB
50.txt AC 4 ms 5652 KiB
51.txt AC 2 ms 4760 KiB
52.txt AC 3 ms 5244 KiB
53.txt AC 4 ms 6040 KiB
54.txt AC 2 ms 4992 KiB
55.txt AC 3 ms 5676 KiB
56.txt AC 3 ms 5916 KiB
57.txt AC 5 ms 6736 KiB
58.txt AC 3 ms 5752 KiB
59.txt AC 4 ms 6380 KiB
60.txt AC 3 ms 5828 KiB
61.txt AC 2 ms 4748 KiB
62.txt AC 2 ms 5480 KiB
63.txt AC 4 ms 6712 KiB
64.txt AC 4 ms 6664 KiB
s1.txt AC 1 ms 4132 KiB
s2.txt AC 1 ms 4204 KiB
s3.txt AC 3 ms 6104 KiB