QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785682#9810. Obliviate, Then Reincarnatehappy_lazier#TL 3ms5604kbC++202.7kb2024-11-26 18:47:542024-11-26 18:47:55

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 18:47:55]
  • Judged
  • Verdict: TL
  • Time: 3ms
  • Memory: 5604kb
  • [2024-11-26 18:47:54]
  • 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<pll> 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, w] : 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,b });
			rev[v].push_back({ u,b });
		}
	}
	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>vis(n + 1, false);
	vector<bool> mark(n + 1, false);
	queue<ll> que;
	rep(i, 1, n) {
		int pre = -1;
		for (auto& [j, w] : g[i]) {
			if (col[j] == col[i]) {
				if (pre == -1)pre = j;
				else if (pre != j) {
					vis[col[i]] = 1;
				}
			}
		}
	}
	vector<bool>vis2(n + 1, false);
	rep(i, 1, n) {
		if (!vis[i] && !vis2[i] && siz[col[i]] > 1) {
			ll res = 0;
			int nown = i;
			vis2[i] = 1;
			while (1) {
				for (auto& [j, w] : g[nown]) {
					if (col[j] != col[i])continue;
					res += w;
					nown = j;
					vis2[j] = 1;
					break;
				}
				if (nown == i)break;
			}
			if (res != 0) {
				vis[col[i]] = 1;
			}
		}
	}
	rep(i, 0, n - 1) {
		if ((vis[col[i]] || slf[i]) && !mark[i]) {
			mark[i] = true;
			for (auto& [v, w] : rev[i]) {
				mark[v] = true;
				que.push(v);
			}
			while (!que.empty()) {
				ll cur = que.front(); que.pop();
				slf[cur] = true;
				for (auto& [v, w] : 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] || vis[col[x]]) 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: 5564kb

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: 2ms
memory: 5604kb

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: 2ms
memory: 3844kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 2ms
memory: 5604kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Time Limit Exceeded

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:


result: