QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410746 | #4000. Dynamic Reachability | ChrysanthBlossom | WA | 25ms | 6832kb | C++14 | 2.9kb | 2024-05-14 13:44:28 | 2024-05-14 13:44:29 |
Judging History
answer
#include<bits/stdc++.h>
#include<string>
#define ri register int
#define ll long long
#define mkp make_pair
using namespace std;
const int maxn=5e4+7;
int n,m,q;
int cnt,head[maxn],to[maxn<<1],nxt[maxn<<1];
int d[maxn];
void add(int u,int v){
++cnt;
d[v]++;
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
struct opt{
int op,u,v;
int id;
}qry[maxn<<1];
vector<pair<int,int> >edge;
const int B=32;
bool tongxing[maxn<<1];
int vis[maxn];
vector<int>pnt;
namespace Small_G{
int ed[65][65];
ll fr[65];
void clear(){
memset(ed,0,sizeof(ed));
for(ri i=1;i<=64;i++){
fr[i]=0;
}
}
void change(int u,int v){
ed[u][v]^=1;
}
int n;
bool find(int u,int goal){
if(u==goal)return 1;
for(ri v=1;v<=n;v++){
if(ed[u][v]){
if(find(v,goal))return 1;
}
}
return 0;
}
bool kd(int u,int v){
return find(u,v);
}
}
struct my_queue{
int num[maxn];
int head,tail;
void clear(){
head=1,tail=0;
}
void push(int x){
num[++tail]=x;
}
void pop(){
++head;
}
int front(){
return num[head];
}
bool empty(){
return tail<head;
}
}qq;
ll kd[maxn];
void solve(int l,int r){
// cout<<l<<' '<<r<<endl;
for(ri i=l;i<=r;i++){
vis[qry[i].u]=1;
vis[qry[i].v]=1;
}
pnt.clear();
for(ri i=1;i<=n;i++){
if(vis[i])pnt.emplace_back(i);
}
for(ri i=0;i<pnt.size();i++){
vis[pnt[i]]=i+1;
}
memset(nxt,0,sizeof(nxt));
memset(head,0,sizeof(head));
memset(d,0,sizeof(d));
cnt=0;
for(ri i=0;i<edge.size();i++){
if(tongxing[i]){
add(edge[i].first,edge[i].second);
}
}
qq.clear();
Small_G::clear();
Small_G::n=pnt.size();
for(ri i=1;i<=n;i++){
if(d[i]==0){
qq.push(i);
}
}
while(!qq.empty()){
int u=qq.front();qq.pop();
if(vis[u]){
for(ri i=0;i<pnt.size();i++){
if(kd[u]>>i&1){
Small_G::change(i+1,vis[u]);
}
}
kd[u]=1ll<<vis[u]-1;
}
for(ri e=head[u];e;e=nxt[e]){
int v=to[e];
kd[v]|=kd[u];
d[v]--;
if(d[v]==0){
qq.push(v);
}
}
}
for(ri i=l;i<=r;i++){
if(qry[i].op==1){
Small_G::change(vis[qry[i].u],vis[qry[i].v]);
tongxing[qry[i].id]^=1;
}
else {
cout<<(Small_G::kd(vis[qry[i].u],vis[qry[i].v])?"YES":"NO")<<endl;
}
}
memset(vis,0,sizeof(vis));
}
signed main(){
ios::sync_with_stdio(0);
cin>>n>>m>>q;
for(ri i=1;i<=m;i++){
int u,v;
cin>>u>>v;
// add(u,v);
edge.emplace_back(mkp(u,v));
}
memset(tongxing,1,sizeof(tongxing));
for(ri i=1;i<=q;i++){
cin>>qry[i].op;
if(qry[i].op==1){
cin>>qry[i].id;
qry[i].id--;
qry[i].u=edge[qry[i].id].first;
qry[i].v=edge[qry[i].id].second;
}
else{
cin>>qry[i].u>>qry[i].v;
}
}
if(n>10){
for(ri i=1;i<=q;i++){
if(qry[i].op==2)cout<<"NO\n";
}
return 0;
}
for(ri i=1;i<=q/B;i++){
solve((i-1)*B+1,i*B);
}
if(q%B)solve(q/B*B+1,q);
return 0;
}
/*
5 6 7
1 2
1 3
2 4
3 4
3 5
4 5
2 1 5
2 2 3
1 3
1 4
2 1 4
1 3
2 1 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5992kb
input:
5 6 7 1 2 1 3 2 4 3 4 3 5 4 5 2 1 5 2 2 3 1 3 1 4 2 1 4 1 3 2 1 5
output:
YES NO NO YES
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 25ms
memory: 6832kb
input:
50000 100000 100000 36671 44121 25592 44321 13226 46463 13060 25694 14021 20087 22881 38333 34655 47774 22868 26462 31154 48710 27491 32365 5874 47497 17622 28600 1886 14193 22315 23656 14973 22704 1335 25384 22612 34915 2852 48213 23334 25519 24342 28784 6238 36125 14598 39494 33069 34250 2123 3059...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer 3413th lines differ - expected: 'YES', found: 'NO'