QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798654 | #9810. Obliviate, Then Reincarnate | IGVA | RE | 4ms | 42772kb | C++14 | 4.5kb | 2024-12-04 15:46:39 | 2024-12-04 15:46:40 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define dep(i,a,b) for(int i=(a),i##_end=(b);i>=i##_end;--i)
using namespace std;
template<class T>inline T mymin(T x,T y){return x<y?x:y;}
template<class T>inline T mymax(T x,T y){return x>y?x:y;}
template <typename T>
inline void read(T &X){
X=0;int w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
if(w) X=-X;
}
const int maxn = 5e5 + 5;
//const double pi = acos(-1.0);
//const double eps = 1e-9;
//const int mo = 1e9 + 7;
int n,m,k,q;
int a[maxn],c[maxn],du[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
vector<int>vc[maxn];
queue<int>Q;
int num;
int l,he[maxn],low[maxn],dfn[maxn],sz[maxn];
int f,sta[maxn],j,ti;
int t,h,sum[maxn];
bool us[maxn];
struct node{
int v,nex;
bool vis;
}e[maxn];
void init(){
t=0;cnt=0;f=0;ti=0;
memset(he,-1,sizeof(he));
memset(dfn,0,sizeof(dfn)); //注意
memset(us,0,sizeof(us));
memset(sum,0,sizeof(sum));
rep(i,0,n) sz[i] = low[i] = du[i] = 0;
}
void add(int u,int v)
{
e[t].v=v;
e[t].vis=0;
e[t].nex=he[u];
he[u]=t++;
}
void tar(int k)
{
low[k]=dfn[k]=++ti;
us[k]=1;
sta[++f]=k;
for(int i=he[k];i!=-1;i=e[i].nex)
{
int v=e[i].v;
if(!dfn[v])
{
tar(v);
low[k]=min(low[k],low[v]);
}
else if(us[v]) low[k]=min(low[k],dfn[v]);
}
if(low[k]==dfn[k])
{
cnt++;
do{
j=sta[f--];
us[j]=0;
sum[j]=cnt;
sz[cnt]++;
}while(j!=k);
}
}
void sol()
{
for(int i=0;i<n;i++)
if(!dfn[i]) tar(i);
}
int X[maxn],Y[maxn],XX[maxn],YY[maxn];
void solve(){
read(n);read(m);read(q);
init();
rep(i,0,n) {
ok[i] = 0;
vc[i].clear();
}
int ct = 0,cct = 0;
rep(i,1,m){
int x,y;
read(x);read(y);
if(y == 0) continue;
if(y % n == 0){
x = (x % n + n) % n;
ok[x] = 1;
continue;
}
if(y > 0){
XX[++cct] = x;
YY[cct] = y;
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
continue;
}
X[++ct] = x;
Y[ct] = y;
}
sol();
rep(i,0,n-1) if(sz[sum[i]] > 1) ok[i] = 1;
// rep(i,1,n) cout<<"debug: "<<i<<" "<<ok[i]<<endl;
init();
rep(i,1,ct){
int x = X[i];
int y = Y[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
}
sol();
rep(i,0,n-1) if(sz[sum[i]] > 1) ok[i] = 1;
init();
rep(i,1,ct){
int x = X[i];
int y = Y[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
}
rep(i,1,cct){
int x = XX[i];
int y = YY[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
}
sol();
rep(i,0,n) c[i] = 0;
rep(i,0,n - 1) if(ok[i]) c[sum[i]] = 1;
rep(i,1,ct){
int x = X[i];
int y = Y[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
}
rep(i,1,cct){
int x = XX[i];
int y = YY[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
if(sum[x] != sum[nxt]) {
du[sum[x]]++;
vc[sum[nxt]].emplace_back(sum[x]);
}
}
rep(i,1,cct){
int x = XX[i];
int y = YY[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
if(sum[x] != sum[nxt]) {
du[sum[x]]++;
vc[sum[nxt]].emplace_back(sum[x]);
}
}
rep(i,1,cnt) if(!du[i]) Q.push(i);
while(!Q.empty()){
int x = Q.front();Q.pop();
for(int v:vc[x]) {
if(c[x]) c[v] = 1;
--du[v];
if(du[v] == 0) Q.push(v);
}
}
rep(i,0,n - 1) if(c[sum[i]]) ok[i] = 1;
rep(i,1,q){
int x;
read(x);
x = (x % n + n) % n;
if(ok[x]) puts("Yes");
else puts("No");
}
// printf("%d\n",ans);
}
int main(){
//cin.tie(0)->sync_with_stdio(false);
int T=1,cas=1;
//read(T);
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 36396kb
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: 4ms
memory: 36600kb
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: 32504kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 42772kb
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...