QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785404#9810. Obliviate, Then Reincarnatehappy_lazier#WA 3ms5664kbC++202.1kb2024-11-26 17:50:312024-11-26 17:50:35

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 17:50:35]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 5664kb
  • [2024-11-26 17:50:31]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rep(i,l,r) for(ll i=l;i<=r;++i)
#define rep_(i,r,l) for(ll i=r;i>=l;--i)
typedef pair<ll, ll> pll;
const ll N = 1e6 + 7;
const ll P = 1e9 + 7;
const ll Inf = 1e18;

ll n, m, dfn[N], low[N], cnt, col[N], stac[N], top;
vector<ll> g[N], rev[N];
bool slf[N], vis[N];

void tarjan(ll cur) {
	low[cur] = dfn[cur] = ++cnt;
	stac[++top] = cur; vis[cur] = true;
	for(auto v : g[cur]) {
		if (!dfn[v]) {
			tarjan(v);
			low[cur] = min(low[cur], low[v]);
		}
		else if (vis[v]) {
			low[cur] = min(low[cur], low[v]);
		}
	}
	if (dfn[cur] == low[cur]) {
		ll node;
		while (node = stac[top--]) {
			col[node] = cur;
			vis[node] = false;
			if (cur == node) break;
		}
	}
}

void solve() {
	ll q;
	cin >> n >> m >> q;
	rep(i, 1, m) {
		ll a, b; cin >> a >> b;
		if (b == 0) continue;
		ll u = (a % n + n) % n;
		ll v = ((a + b) % n + n) % n;
		//cout << u << " ---> " << v << endl;
		if (u == v) slf[u] = true;
		else {
			g[u].push_back(v);
			rev[v].push_back(u);
		}
	}
	rep(i, 0, n - 1) {
		if (!dfn[i]) tarjan(i);
	}
	map<ll, ll> siz;
	rep(i, 0, n - 1) siz[col[i]]++;
	/*map<ll, vector<ll>> debg;
	rep(i, 0, n - 1) debg[i].push_back(i);
	for (auto& [cc, vec] : debg) {
		cout << "col " << cc << " :   ";
		for (auto v : vec) cout << v << " , ";
		cout << endl;
	}*/

	vector<bool> mark(n + 1, false);
	queue<ll> que;
	rep(i, 0, n - 1) {
		if ((siz[col[i]] > 1 || slf[i]) && !mark[i]) {
			mark[i] = true;
			for (auto v : rev[i]) {
				mark[v] = true;
				que.push(v);
			}
			while (!que.empty()) {
				ll cur = que.front(); que.pop();
				slf[cur] = true;
				for (auto v : rev[cur]) {
					if (!mark[v]) {
						mark[v] = true;
						que.push(v);
					}
				}
			}
		}
	}

	while (q--) {
		ll x; cin >> x;
		x = (x % n + n) % n;
		if (slf[x] || siz[col[x]] > 1) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

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

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 5608kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 5664kb

input:

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

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'