QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788861#9810. Obliviate, Then ReincarnateCodeChildWA 0ms3832kbC++203.6kb2024-11-27 18:33:112024-11-27 18:33:15

Judging History

This is the latest submission verdict.

  • [2024-11-27 18:33:15]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3832kb
  • [2024-11-27 18:33:11]
  • Submitted

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'