QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789291#9810. Obliviate, Then ReincarnatemasttfWA 0ms3808kbC++202.5kb2024-11-27 19:47:182024-11-27 19:47:25

Judging History

This is the latest submission verdict.

  • [2024-11-27 19:47:25]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3808kb
  • [2024-11-27 19:47:18]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define dbg(x...) \
do { \
    cout << #x << " -> "; \
    err(x); \
} while (0)

void err() {
    cout << endl << endl;
}
 
template<class T, class... Ts>
void err(T arg, Ts ... args) {
    cout << fixed << setprecision(10) << arg << ' ';
    err(args...);
}
void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>> g(n);
    vector<int> inf(n);
    for(int i = 1; i <= m; i++){
    	int u, d; cin >> u >> d;
    	if(d == 0)continue;
    	u = (u % n + n) % n;
    	int v = (((u + d) % n) + n) % n;
    	if(u == v){
    		if(d % n == 0){
    			inf[u] = 1;
    		}else{
    			if(d < 0){
    				v = (u + n - 1) % n;
    			}else{
    				v = (u + 1) % n;
    			}
    			g[u].push_back(v);
    		}
    	}else{
    		g[u].push_back(v);
    	}
    	
    }
    int tot = 0, cnt = 0;
    vector<int> dfn(n), low(n);
    vector<int> stk;
    vector<int> bl(n), val(n + 1);
    auto tarjan = [&](auto self, int now) -> void{
    	dfn[now] = low[now] = ++tot;
    	stk.push_back(now);
    	for(auto v : g[now]){
    		if(!dfn[v]){
    			self(self, v);
    			low[now] = min(low[now], low[v]);
    		}else if(!bl[v]){
    			low[now] = min(low[now], dfn[v]);
    		}
    	}
    	if(dfn[now] == low[now]){
    		cnt++;
    		int num = 0;
    		int y;
    		// dbg(cnt);
    		do{
    			y = stk.back();
    			stk.pop_back();
    			// dbg(y);
    			bl[y] = cnt;
    			val[cnt] |= inf[y];
    			num++;
    		}while(y != now);
    		if(num >= 2)val[cnt] = 1;
    	}
    };
    for(int i = 0; i < n; i++){
    	if(!dfn[i]){
    		tarjan(tarjan, i);
    	}
    }
    vector<vector<int>>G(cnt + 1);
    for(int i = 0; i < n; i++){
    	for(auto v : g[i]){
    		if(bl[i] == bl[v])continue;
    		// dbg(bl[v], bl[i]);
    		G[bl[v]].push_back(bl[i]);
    	}
    }
    auto bfs = [&]() -> void{
    	queue<int> q;
    	for(int i = 1; i <= cnt; i++){
    		if(val[i])q.push(i);
    	}
    	while(!q.empty()){
    		int u = q.front();
    		// dbg(u);
    		q.pop();
    		for(auto v : G[u]){
    			if(val[v])continue;
    			val[v] = 1;
    			q.push(v);
    		}
    	}
    };
    bfs();
    for(int i = 1; i <= q; i++){
    	int x; cin >> x;
    	x = (x % n + n) % n;
    	if(val[bl[x]])cout << "Yes\n";
    	else cout << "No\n";
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; // cin >> t;
    while(t--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

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: 3808kb

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: 3524kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3752kb

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'