NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#214388	#2678. Small Multiple	one_zero_four_zero	85	6206ms	169576kb	C++11	976b	2024-11-18 19:38:32	2024-11-19 08:29:09

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

struct edge{
	int v, w;
};

int K, M;
vector<edge> E[1000006];
int dis[1000006];
bool vis[1000006];

void dijkstra(){
	memset(dis, 0x3f, sizeof(dis));
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	for (int j = 1; j < M; j ++){
		dis[j] = j;
		q.push({j, j});
	}
	while (!q.empty()){
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto && i : E[u]){
			int v = i.v, w = i.w;
			if (dis[v] <= dis[u] + w) continue;
			dis[v] = dis[u] + w;
			q.push({dis[v], v});
		}
	}
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif

	scanf("%d %d", &K, &M);
	for (int i = 0; i < K; i ++){
		for (int j = 0; j < M; j ++){
			E[i].push_back({(i * M + j) % K, j});
		}
	}
	dijkstra();
	printf("%d\n", dis[0]);

    return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 5

Accepted

time: 8ms

memory: 28592kb

input:

32 4

output:

result:

ok single line: '1'

Test #2:

score: 5

Accepted

time: 0ms

memory: 28596kb

input:

25 6

output:

result:

ok single line: '5'

Test #3:

score: 5

Accepted

time: 4ms

memory: 28596kb

input:

19 3

output:

result:

ok single line: '2'

Test #4:

score: 5

Accepted

time: 9ms

memory: 28596kb

input:

64 7

output:

result:

ok single line: '4'

Test #5:

score: 5

Accepted

time: 8ms

memory: 28612kb

input:

86 10

output:

result:

ok single line: '3'

Test #6:

score: 5

Accepted

time: 8ms

memory: 28584kb

input:

17 2

output:

result:

ok single line: '2'

Test #7:

score: 5

Accepted

time: 808ms

memory: 169576kb

input:

937761 10

output:

result:

ok single line: '6'

Test #8:

score: 5

Accepted

time: 540ms

memory: 99196kb

input:

788944 8

output:

result:

ok single line: '4'

Test #9:

score: 5

Accepted

time: 295ms

memory: 60028kb

input:

573314 3

output:

result:

ok single line: '4'

Test #10:

score: 0

Time Limit Exceeded

input:

785883 5

output:

result:

Test #11:

score: 5

Accepted

time: 898ms

memory: 97620kb

input:

769025 7

output:

result:

ok single line: '6'

Test #12:

score: 5

Accepted

time: 456ms

memory: 80328kb

input:

909894 4

output:

result:

ok single line: '3'

Test #13:

score: 5

Accepted

time: 417ms

memory: 119692kb

input:

585472 9

output:

result:

ok single line: '8'

Test #14:

score: 5

Accepted

time: 551ms

memory: 95484kb

input:

795020 5

output:

result:

ok single line: '4'

Test #15:

score: 5

Accepted

time: 583ms

memory: 77504kb

input:

514716 8

output:

result:

ok single line: '3'

Test #16:

score: 0

Time Limit Exceeded

input:

984458 5

output:

result:

Test #17:

score: 5

Accepted

time: 446ms

memory: 51288kb

input:

645285 2

output:

result:

ok single line: '4'

Test #18:

score: 5

Accepted

time: 655ms

memory: 135104kb

input:

694328 9

output:

result:

ok single line: '8'

Test #19:

score: 5

Accepted

time: 520ms

memory: 92068kb

input:

698907 6

output:

result:

ok single line: '2'

Test #20:

score: 0

Time Limit Exceeded

input:

994036 7