QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788417#9810. Obliviate, Then ReincarnateLGyxjWA 231ms56868kbC++142.6kb2024-11-27 16:51:372024-11-27 16:51:37

Judging History

This is the latest submission verdict.

  • [2024-11-27 16:51:37]
  • Judged
  • Verdict: WA
  • Time: 231ms
  • Memory: 56868kb
  • [2024-11-27 16:51:37]
  • Submitted

answer

//////////////////////////
// Author: lnyxj
// Time: 2024-11-27 16:20:18
///////////////////////////
#include <bits/stdc++.h>
#define xx first
#define yy second
// #define int long long
// #define double long double
using namespace std;
const int N = 5e5 + 5, mod = 998244353, inv2 = mod + 1 >> 1, inf = 0x3f3f3f3f;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef long long ll;

int n, m, qs;
int a[N];

int num, h[N], to[N], w[N], nxt[N];
inline void adde(int x, int y, int z) { ++ num; nxt[num] = h[x]; w[num] = z; to[num] = y; h[x] = num; }

stack<int> stk;
int low[N], pre[N], dfn;
int col[N], cnt;
bool tst[N];

bool solvec(const vector<int>& pts) {
	static vector<pii> edgs[N];
	static bool vis[N];
	static int dis[N];
	for (int v : pts) {
		dis[v] = -1; vis[v] = 0;
		for (int i = h[v]; i; i = nxt[i]) 
			if (col[to[i]] == col[v]) edgs[v].push_back({to[i], w[i]});
	}
	priority_queue<pii, vector<pii>, greater<pii> > q;
	q.push({pts[0], dis[pts[0]] = 0});
	while (!q.empty()) {
		const auto [x, d] = q.top(); q.pop();
		if (vis[x]) continue;
		vis[x] = 1;
		for (auto [y, w] : edgs[x]) {
			if (dis[y] == -1) dis[y] = d + w;
			else if (dis[y] != d + w) return 1;
		}
	}
	return 0;
}

void tarjan(int x) {
	stk.push(x);
	low[x] = pre[x] = ++ dfn;
	for (int i = h[x]; i; i = nxt[i]) {
		const int y = to[i];
		if (!pre[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} else low[x] = min(low[x], pre[y]);
	}
	if (low[x] >= pre[x]) {
		int p = -1; ++ cnt;
		vector<int> cur;
		while (p != x) {
			p = stk.top(); stk.pop();
			col[p] = cnt;
			cur.push_back(p);
		}
		tst[cnt] = solvec(cur);
	}
}

void solve() {
	cin >> n >> m >> qs;
	for (int i = 1, x, y; i <= m; ++ i) {
		cin >> x >> y;
		adde(((x % n) + n) % n, ((x + y) % n + n) % n, y);
	}
	for (int i = 0; i < n; ++ i) 
		if (!pre[i]) tarjan(i);
	static vector<int> edgx[N];
	static int d[N];
	for (int i = 0; i < n; ++ i) {
		for (int j = h[i]; j; j = nxt[j]) {
			const int p = to[j];
			if (col[i] != col[p]) {
				edgx[col[p]].push_back(col[i]);
				++ d[col[i]];
			}
		}
	}
	queue<int> q;
	for (int i = 1; i <= cnt; ++ i) 
		if (!d[i]) q.push(i);
	while (!q.empty()) {
		const int x = q.front(); q.pop();
		for (int y : edgx[x]) {
			-- d[y];
			tst[y] |= tst[x];
			if (!d[y]) 
				q.push(y);
		}
	}
	for (int i = 1, x; i <= qs; ++ i) 
		cin >> x, cout << "No\n\0Yes\n" + (tst[col[(x % n + n) % n]]) * 4;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1;
	while (T --) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 38312kb

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: 36388kb

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: 6ms
memory: 36220kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 3ms
memory: 39024kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: 0
Accepted
time: 197ms
memory: 52056kb

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:

ok 500000 tokens

Test #6:

score: -100
Wrong Answer
time: 231ms
memory: 56868kb

input:

100848 500000 500000
720352587 361776806
231853504 -933882325
960971230 -83519300
-152772415 -631132247
842871215 -666621297
857194330 -754943024
-698506963 -705416545
-3551931 -927937446
628710320 -942247987
674921043 847145884
-325629529 475694308
-339363446 686789318
236702996 654762989
420412365...

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 1st words differ - expected: 'Yes', found: 'No'