QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#788696 | #9810. Obliviate, Then Reincarnate | lilab# | WA | 1ms | 5912kb | C++20 | 3.1kb | 2024-11-27 17:56:32 | 2024-11-27 17:56:32 |
Judging History
answer
#include<bits/stdc++.h>
// using namespace std;
using ll=long long;
#define int ll
const ll N=5e5+100;
struct gra{
struct data{ int to, next, w; };
std::vector<int> head;
std::vector<data> e;
int tot;
void ini( int n ){
head.clear();e.clear();
head.resize( n + 1 );e.resize( 1 );
tot = 0;
}
void add_e( int x, int y, int w = 1 ){
e.push_back({y, head[ x ], w });
head[ x ] = ++tot;
}
}g, g1;
int n, m, Q ;
int dfn[ N ], low[ N ], dfnnum;
std::vector<int> st;
int ins[ N ], scc[ N ], scccnt, size[ N ];
void tarjan( int x ){
st.push_back( x );
ins[ x ] = 1;
dfn[ x ] = low[ x ] = ++dfnnum;
for( int i = g.head[ x ] ; i ; i = g.e[ i ].next ){
int y = g.e[ i ].to;
if( !dfn[ y ] ){
tarjan( y );
low[ x ] = std::min( low[ x ], low[ y ] );
}else{
if( ins[ y ] ) low[ x ] = std::min( low[ x ], dfn[ y ] );
}
}
if( dfn[ x ] == low[ x ] ){
int y ; ++scccnt;
do{
y = st.back();ins[ y ] = 0;
st.pop_back();
scc[ y ] = scccnt;
size[ scccnt ] ++;
}while( x != y );
}
}
std::vector<std::pair<int,int>> es;
void solve(){
std::cin>>n>>m>>Q;
g.ini( n );
std::vector<int> selfloop( n + 1 );
for( int i = 1 ; i <= m ; i ++ ){
int x, y;std::cin>>x>>y;
if( y == 0 ) continue;
y += x;
x = (x % n + n) % n;
y = (y % n + n) % n;
x ++;
y ++;
es.push_back( {x, y});
g.add_e( x, y );
if( x == y ) selfloop[ x ] = 1;
}
for( int i = 1 ; i <= n ; i ++ ){
if( !dfn[ i ] ) tarjan( i );
}
g1.ini( scccnt );
std::vector<int> bj( scccnt + 1 ), in( scccnt + 1 );
for( int i = 1 ; i <= n ; i ++ ){
if( size[ scc[ i ] ] != 1 || selfloop[ i ] ) bj[ scc[ i ] ] = 1;
}
for( auto t : es ){
if( scc[ t.first ] == scc[ t.second ] ) continue;
g1.add_e( scc[ t.second ], scc[ t.first ] );
in[ scc[ t.first ] ] ++;
}
std::queue<int> q;
for( int i = 1 ; i <= scccnt ; i ++ ){
if( in[ i ] == 0 ){
q.push( i );
}
}
while( q.size() ){
int x = q.front();
q.pop();
for( int i = g1.head[ x ]; i; i = g1.e[ i ].next ){
int y = g1.e[ i ].to;
bj[ y ] |= bj[ x ];
}
}
std::vector<int> ans( n + 1 );
for( int i = 1 ; i <= n ; i ++ ){
if( bj[ scc[ i ] ] ) ans[ i ] = 1;
}
while( Q-- ){
int x;std::cin>>x;
x = ( x % n + n ) % n;
x ++;
if( ans[ x ] ){
std::cout<<"Yes\n";
}else{
std::cout<<"No\n";
}
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t_=1;
// std::cin>>t_;
while(t_--)solve();
}
/*
3 2 3
1 1
-1 3
1
2
3
3 2 3
1 1
-1 0
1
2
3
3 3 3
1 1
2 2
1 2
1
2
3
3 3 3
1 1
2 2
3 1
1
2
3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5636kb
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: 1ms
memory: 5912kb
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: 1ms
memory: 5624kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5632kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No Yes No
result:
wrong answer 2nd words differ - expected: 'No', found: 'Yes'