QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795838 | #9810. Obliviate, Then Reincarnate | ucup-team191# | RE | 3ms | 9160kb | C++23 | 1.6kb | 2024-12-01 02:17:29 | 2024-12-01 02:17:31 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...