QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788861 | #9810. Obliviate, Then Reincarnate | CodeChild | WA | 0ms | 3832kb | C++20 | 3.6kb | 2024-11-27 18:33:11 | 2024-11-27 18:33:15 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <cstdio>
#include <unordered_map>
#include <deque>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <array>
#include <bitset>
#include <limits.h>
#include <numeric>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll ;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<int ,PII> PIII ;
typedef pair<int, pair<PII ,int > > PIIII;
typedef pair<LL , LL> PLL ;
typedef pair<LL ,int > PLI ;
typedef pair<int,char > PIC ;
typedef unsigned long long ULL ;
const int N = 5e5+10,M = 4e5+10 ;
const LL mod = 1e9+7 , INF = 1e18+10;
const int inf = 1e8 ;
const double eps = 1e-7 ;
const ULL P= 131 ;
LL n , m , k ;
class Scc {
public :
int size ;
vector< vector<int> > adj ;
stack<int> stk ;
vector<int> dfn , low ,id ;
vector<bool > st ;
vector< vector<int> > scc ;
int timestop ,cnt ;
Scc( ):size( 0 ) { }
Scc( int _size) : size(_size) , dfn(_size+1, 0 ) ,low(_size+1, 0 ) , id(_size+1 , 0) ,st( _size + 1, false) , adj(_size+1) ,scc(_size+1) ,timestop(0) ,cnt(0){}
Scc( const Scc &_t) {
size = _t.size ; stk = _t.stk ; dfn = _t.dfn ;low = _t.low;id = _t.id;
st = _t.st ; timestop = _t.timestop ; cnt = _t.cnt ; scc =_t.scc ;
}
~Scc( ) { dfn.clear( ) ; low.clear() ; id.clear() ; st.clear() ; scc.clear() ;while(!stk.empty()) stk.pop( ); }
void addedges(int a, int b ) {
adj[a].push_back( b) ;
}
void run( ) {
for(int i=1; i <=size; ++ i) if(!dfn[i]) tarjan( i) ;
}
void tarjan(int u ) {
stk.push( u ) ; st[u] = true ;
dfn[u] = low[u] = ++ timestop ;
for(auto son : adj[u]) {
if( !dfn[son]) {
tarjan( son) ;
low[u] = min( low[u] ,low[son]) ;
}else if( st[son]) low[u] =min( low[u] ,dfn[son]) ;
}
if( low[u] == dfn[u] ) {
int v ;
++cnt ;
do{
v = stk.top() ; stk.pop() ;
id[v] = cnt ;
scc[cnt].push_back( v) ;
st[v] = false ;
}while( v !=u ) ;
}
}
bool same( int a, int b ) {
return id[a] == id[b] ;
}
int getsize(int x ) { return scc[x].size() ;}
};
void solve( ) {
cin >> n >> m >> k ;
Scc scc(n) ;
vector< vector< array<int,2> >> adj( n + 1 ) ;
for(int i = 1 ; i <= m ; ++ i ) {
int u , w , v ;
cin >> u >> w ;
v = ( ( u + w ) % n + n ) % n + 1 ;
u = ( u % n + n ) % n + 1 ;
scc.addedges(u , v ) ;
adj[u].push_back( { v , w }) ;
}
scc.run() ;
auto SCC = scc.scc ;
auto id = scc.id ;
vector<bool> st( scc.cnt + 1 ) ;
vector<LL> dis( n + 1 , - INF ) ;
for(int i = 0 ; i < SCC.size() ; ++ i ) {
auto &S = SCC[i] ;
if( S.empty()) continue ;
dis[S[0]] = 0 ;
auto dfs =[&](auto self ,int u )->bool {
for(auto [ v , w ] : adj[u] ) {
if( id[v] != id[u] ) continue ;
if( dis[v] == INF ) {
dis[v] = dis[u] + w ;
if( self( self , v ) )
return true ;
}else if( dis[v] != dis[u] + w )
return true ;
}
return false ;
} ;
st[i] = st[i] | dfs( dfs , S[0] ) ;
for(auto &u : S ) {
for(auto &[v , _ ] : adj[u] ) {
st[i] = st[ id[v] ] | st[i] ;
}
}
}
while( k -- ) {
int x ; cin >> x ;
x = ( x % n + n ) % n + 1 ;
// cout <<"Query " << x << '\n' ;
if( st[id[x]] ) cout <<"Yes\n";
else cout <<"No\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie( 0 ) ; cout.tie(0) ;
int T = 1 ;
// cin >> T ;
while(T-- ){
solve() ;
}
return 0 ;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3832kb
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: 3596kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3816kb
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'