QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#795838#9810. Obliviate, Then Reincarnateucup-team191#RE 3ms9160kbC++231.6kb2024-12-01 02:17:292024-12-01 02:17:31

Judging History

This is the latest submission verdict.

  • [2024-12-01 02:17:31]
  • Judged
  • Verdict: RE
  • Time: 3ms
  • Memory: 9160kb
  • [2024-12-01 02:17:29]
  • Submitted

answer

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 5e5 + 500;

vector < pii > v[N];
vector < int > r[N];

stack < int > S;
int bio[N], col[N], grupa, targ[N];
int n, m, q;
ll pot[N];


void dfs1(int x) {
	if(bio[x]) return;
	bio[x] = 1;
	for(auto &[y, w] : v[x]) {
		dfs1(y);
	}
	S.push(x);
}

void dfs2(int x) {
	if(col[x]) return;
	col[x] = grupa;
	for(int y : r[x]) 
		dfs2(y);
}

void scc() {
	for(int i = 0;i < n;i++) dfs1(i);
	for(;!S.empty();S.pop()) {
		if(!col[S.top()]) {
			grupa++; dfs2(S.top());	
		}
	}
}

void dfs3(int x) {
	if(bio[x]) return;
	bio[x] = 1;
	for(auto &[y, w] : v[x]) {
		if(col[y] != col[x]) continue;
		pot[y] = pot[x] + w;
		dfs3(y);
	}
}

void dfs4(int x) {
	if(targ[x]) return;
	targ[x] = 1;
	for(int y : r[x])
		dfs4(y);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 0;i < m;i++) {
		int a, b; scanf("%d%d", &a, &b);
		a = (a % n + n) % n;
		v[a].PB({(a + b) % n, b});
		r[(a + b) % n].PB(a);
	//	printf("%d - (%d) > %d\n", a, v[a].back().Y, v[a].back().X);
	}
	scc();
	memset(bio, 0, sizeof(bio));
	for(int i = 0;i < n;i++) {
		if(bio[i]) continue;
		dfs3(i);
	}
	for(int x = 0;x < n;x++) {
		bool mogu = false;
		for(auto &[y, w] : v[x]) {
			if(col[y] == col[x] && pot[y] - pot[x] != w) mogu = true;
		}
		if(mogu) dfs4(x);
	}
	for(;q--;) {
		int x; scanf("%d", &x);
		printf(targ[(x % n + n) % n] ? "Yes\n" : "No\n");
	}
	return 0;
}

詳細信息

Test #1:

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Runtime Error

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: