QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#107503	#5573. Holiday Regifting	FISHER_	WA	14ms	4128kb	C++14	1.1kb	2023-05-21 17:37:52	2023-05-21 17:37:55

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-21 17:37:55]
评测

测评结果：WA
用时：14ms
内存：4128kb

查看

[2023-05-21 17:37:52]
提交

answer

#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
#define gcd(x, y) __gcd(x, y)
using namespace std;
typedef long long i64;
const int maxn = 10000;
int c[maxn + 5];
vector<int> g[maxn + 5];
int ind[maxn + 5];
int V[maxn + 5];
int tp[maxn + 5];
i64 ca[maxn + 5];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].PB(v);
	}
	queue<int> q;
	for (int i = 1; i <= n; i++)
		if (!ind[i]) q.push(i);
	int cnt = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		tp[++cnt] = u;
		for (int v : g[u])
			if (!(--ind[v])) q.push(v);
	}
	i64 ans = c[1];
	for (int v : g[1]) V[v] = 1;
	for (int i = 2; i <= n; i++) {
		int u = tp[i];
		if (!V[u]) continue;
		int t = c[u] / gcd(c[u], V[u]);
		ans *= t;
		memset(ca, 0, sizeof(ca));
		for (int j = 1; j <= n; j++) {
			int u2 = tp[j];
			i64 p = 1LL * V[u2] * t + ca[u2];
			V[u2] = p % c[u2];
			for (int v : g[u2]) ca[v] += p / c[u2];
		}
	}
	printf("%lld", ans);
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 3872kb

input:

output:

result:

ok 1 number(s): "24"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3892kb

input:

3 0
95 13 77

output:

result:

ok 1 number(s): "95"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3960kb

input:

12 14
6 7 17 16 20 14 17 16 6 11 6 14
4 11
3 5
2 5
9 11
7 12
1 3
5 9
3 7
3 8
4 9
1 9
4 7
2 11
1 12

output:

result:

ok 1 number(s): "8739360"

Test #4:

score: 0

Accepted

time: 2ms

memory: 3876kb

input:

1 0
2

output:

result:

ok 1 number(s): "2"

Test #5:

score: 0

Accepted

time: 2ms

memory: 3924kb

input:

50 97
2 2 2 2 2 11 13 7 2 2 2 2 2 2 5 2 5 2 3 2 2 2 2 2 2 2 2 13 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
17 26
17 24
17 38
15 28
23 28
45 50
16 28
7 37
7 31
5 28
2 28
13 28
6 40
3 40
3 7
44 46
11 40
12 28
15 29
15 17
28 49
5 48
6 19
28 41
7 17
27 28
33 38
26 28
2 39
32 40
8 17
17 28
28 42
6 46
2...

output:

result:

ok 1 number(s): "68640"

Test #6:

score: -100

Wrong Answer

time: 14ms

memory: 4128kb

input:

500 30000
109 118 125 106 124 114 125 118 110 113 121 132 102 113 117 118 131 104 113 116 113 114 98 134 123 135 124 124 105 105 98 108 118 109 105 117 109 104 109 116 100 112 106 109 113 103 113 108 111 97 125 96 102 106 130 107 111 94 124 104 109 113 101 100 95 105 101 100 106 100 106 86 105 83 11...

output:

result:

wrong answer 1st numbers differ - expected: '442991751', found: '0'