oj.uz

Submission #1042977

# Submission time Handle Problem Language Result Execution time Memory
1042977 2024-08-03T16:35:00 Z XJP12 Werewolf (IOI18_werewolf) C++14
7 / 100
 4000 ms 29552 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi ;
vvi g;
bitset<200005> vis;
bool ban=false;
bool hw=false;
void dfs(int u, int l, int r, int j, int fin){
	vis[u]=true;
	if(u==j && u<=r){
		ban=true;
	}
	if(u==fin && ban==true){
		hw=true;
	}
	for(auto v: g[u]){
		if(u==j && u>r) break;
		if(!vis[v]){
			if(!ban){
				if(v>=l) dfs(v,l,r,j, fin);
			}else{
				if(v<=r) dfs(v,l,r,j, fin);
			}
		}
	}
	if(u==j){
		ban=false;
	}
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r){
	int m = (int)x.size();
	int q = (int)e.size();
	vi ans(q,0);
	g.resize(n, vi());
	for(int i=0; i<m; i++){
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	for(int i=0; i<q; i++){
		for(int j=0; j<n; j++){
			if(j<l[i] || j>r[i]) continue;
		    ban=false;
			hw=false;
			vis.reset();
			dfs(s[i], l[i], r[i], j, e[i]);
			if(vis[e[i]]==true && hw==true){
				ans[i]=1;
			}
		}
	}
	return ans;

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Execution timed out 4058 ms 904 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4017 ms 29552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 7 ms 476 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Execution timed out 4058 ms 904 KB Time limit exceeded
11 Halted 0 ms 0 KB -