Submission #2117580


Source Code Expand

Copy
#include <iostream>
#include <set>
#include <deque>
#include <vector>
using namespace std;

typedef long long i64;

i64 k;

i64 dist[100010];

struct edge
{
	int to;
	int cost;
};

vector<edge> edges[100010];


int main()
{
	cin >> k;

	for(int i = 0;i < k;i++)
	{
		{
			//plus 1
			int n = i + 1;
			n = n % k;

			edges[i].push_back({n,1});
		}
		{
			//plus * 10

			int n = i * 10;
			n = n % k;
			edges[i].push_back({n,0});
		}
	}
	typedef pair<i64,int> P;

	deque<P> que;
	que.push_back({1,1});
	fill(dist , dist + 100010,(1LL <<60));
	dist[1] = 1;

	while(!que.empty())
	{
		i64 d = que.front().first;
		int v = que.front().second;

		que.pop_front();

		if(dist[v] < d) continue;

		for(edge& e : edges[v])
		{
			if(dist[e.to] > dist[v] + e.cost)
			{
				dist[e.to] = dist[v] + e.cost;
				if(e.cost == 0)
				{
					que.push_front({dist[e.to],e.to});
				}
				else
				{
					que.push_back({dist[e.to],e.to});
				}
			}
		}
	}

	cout << dist[0] << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Small Multiple
User niuez
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1062 Byte
Status
Exec Time 20 ms
Memory 7296 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 700 / 700 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
Case Name Status Exec Time Memory
01.txt 3 ms 3456 KB
02.txt 3 ms 3328 KB
03.txt 3 ms 3328 KB
04.txt 3 ms 3328 KB
05.txt 3 ms 3328 KB
06.txt 3 ms 3328 KB
07.txt 3 ms 3328 KB
08.txt 3 ms 3328 KB
09.txt 3 ms 3328 KB
10.txt 3 ms 3328 KB
11.txt 3 ms 3328 KB
12.txt 3 ms 3328 KB
13.txt 3 ms 3328 KB
14.txt 3 ms 3328 KB
15.txt 3 ms 3328 KB
16.txt 3 ms 3328 KB
17.txt 3 ms 3456 KB
18.txt 3 ms 3328 KB
19.txt 3 ms 3328 KB
20.txt 3 ms 3328 KB
21.txt 17 ms 6656 KB
22.txt 17 ms 6656 KB
23.txt 19 ms 7296 KB
24.txt 20 ms 7168 KB
25.txt 19 ms 6912 KB
26.txt 20 ms 6784 KB
27.txt 18 ms 7296 KB
28.txt 19 ms 7040 KB
29.txt 19 ms 6912 KB
30.txt 20 ms 7168 KB
31.txt 3 ms 3328 KB
32.txt 3 ms 3328 KB
33.txt 16 ms 6272 KB
34.txt 8 ms 4864 KB
35.txt 15 ms 6016 KB
36.txt 17 ms 6656 KB
37.txt 6 ms 4224 KB
38.txt 9 ms 4736 KB
39.txt 11 ms 5248 KB
40.txt 4 ms 3584 KB
41.txt 16 ms 6272 KB
42.txt 18 ms 6784 KB
43.txt 5 ms 3840 KB
44.txt 3 ms 3456 KB
45.txt 11 ms 5120 KB
46.txt 12 ms 5504 KB
47.txt 4 ms 3584 KB
48.txt 18 ms 6400 KB
49.txt 16 ms 6272 KB
50.txt 11 ms 5248 KB
51.txt 6 ms 4096 KB
52.txt 9 ms 4864 KB
53.txt 14 ms 5760 KB
54.txt 8 ms 4480 KB
55.txt 11 ms 5120 KB
56.txt 13 ms 5760 KB
57.txt 18 ms 6656 KB
58.txt 12 ms 5376 KB
59.txt 15 ms 6016 KB
60.txt 12 ms 5504 KB
61.txt 5 ms 3968 KB
62.txt 10 ms 4992 KB
63.txt 17 ms 6656 KB
64.txt 17 ms 6656 KB
s1.txt 3 ms 3328 KB
s2.txt 3 ms 3328 KB
s3.txt 14 ms 6016 KB