QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788711#9810. Obliviate, Then Reincarnatewangjunrui#WA 86ms15072kbC++141.7kb2024-11-27 18:00:242024-11-27 18:00:25

Judging History

This is the latest submission verdict.

  • [2024-11-27 18:00:25]
  • Judged
  • Verdict: WA
  • Time: 86ms
  • Memory: 15072kb
  • [2024-11-27 18:00:24]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, m, q;
struct Edge
{
	int next, to, dis;
} edge[N];
int head[N], num_edge;
inline void add_edge(int from, int to, int dis)
{
	edge[++num_edge].next = head[from];
	edge[num_edge].to = to;
	edge[num_edge].dis = dis;
	head[from] = num_edge;
}
int dfn[N], low[N], dfstime;
int st[N], top;
bool dp[N], answer[N];
long long dis[N];
int belong[N], color;
inline void tarjan(int u)
{
	st[++top] = u;
	dfn[u] = low[u] = ++dfstime;
	for (int i = head[u]; i; i = edge[i].next)
	{
		int v = edge[i].to;
		if (!dfn[v])
		{
			dis[v] = dis[u] + edge[i].dis;
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (!belong[v])
		{
			low[u] = min(low[u], dfn[v]);
			if (dis[v] != dis[u] + edge[i].dis)
				dp[v] = true;
		}
		dp[u] |= dp[v];
	}
	if (dfn[u] == low[u])
	{
		answer[belong[u] = ++color] |= dp[u];
		while (st[top] != u)
		{
			answer[belong[st[top]] = color] |= dp[st[top]];
			--top;
		}
	}
}
inline void _main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i)
	{
		int u, v;
		cin >> u >> v;
		add_edge((u % n + n) % n, ((u + v) % n + n) % n, v);
	}
	for (int i = 0; i < n; ++i)
		if (!dfn[i])
			tarjan(i);
	for (int i = 0; i < n; ++i)
	{
		int x;
		cin >> x;
		cout << (answer[belong[(x % n + n) % n]] ? "Yes\n" : "No\n");
	}
	num_edge = color = dfstime = 0;
	for (int i = 0; i < n; ++i)
	{
		belong[i] = 0;
		head[i] = 0;
		answer[i] = dp[i] = 0;
		dis[i] = 0;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
//	cin >> test;
	while (test--)
		_main();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5672kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

Yes
Yes
No

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 7792kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 7792kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5748kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Wrong Answer
time: 86ms
memory: 15072kb

input:

50134 500000 500000
-154428638 -283522863
-186373509 -327130969
154999046 46750274
-933523447 349415487
-437683609 140099255
864996699 -262318199
811293034 -264299324
120273173 52410685
874944410 -52048424
445049930 -803690605
-138111276 -104634331
720288580 126597671
471164416 -348777147
-356502322...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer Unexpected EOF in the participants output