oj.uz

Submission #623647

# Submission time Handle Problem Language Result Execution time Memory
623647 2022-08-06T08:22:12 Z l_reho Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 35476 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

/*
 
 dati due nodi di inizio e fine,
 sicuramente ci sarà un path o più path
 che li collegano, noi stiamo cercando un path in particolare
 colui che è decrescente
 
 TUTTO CIO NON E UN ALBERO
 * 
 posso modificare BFS + subtask3 con ST e fare 49 punti.
 
 */

vector<vector<int>> graph;


bool solver(int start, int end, int L, int R, int N){
	
	vector<vector<bool>> visited(N, vector<bool>(2, 0));
	
	
	queue<pair<int, bool>> q;
	q.push({start, 1});
	
	if(start >= L && start <= R) q.push({start, 0});
	
	while(!q.empty()){
		pair<int, bool> curr = q.front();
		q.pop();
		
		int node = curr.first;
		bool human = curr.second;
		
		vector<int> adj = graph[node];
		
		visited[node][human] = true;
		
		// cout<<"DEBUG-->"<<start<<" "<<node<<" "<<human<<endl;
		
		for(int a : adj){
			if(human){
				// cout<<"DEBUG-->"<<start<<" "<<a<<" "<<L<<endl;
				if(a < L) continue;
				
				if(a >= L && a <= R && !visited[a][0]){
					q.push({a, 0});
					visited[a][0] = true;
				}
				
				if(visited[a][1]) continue;
				
				q.push({a, 1});
				visited[a][1] = true;
				
			}else{
				if(a > R) continue;
				
				if(visited[a][0]) continue;
				q.push({a, 0});
				visited[a][0] = true;
				
			}
		}
	}
	
	if(visited[end][1] && end >= L && end <= R) return 1;
	return visited[end][0];
}
/*

6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
 
 
 
 */

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
	int M = X.size();
	int Q = L.size();
	
	vector<int> ans(Q);
	graph.assign(N, vector<int>());

	for(int i = 0; i < M; i++){
		graph[X[i]].push_back(Y[i]);
		graph[Y[i]].push_back(X[i]);
	}


	
	for(int i = 0; i < Q; i++){
		// adesso abbiamo L[i] ed R[i]
		ans[i] = solver(S[i], E[i], L[i], R[i], N);
		
	}
	
	return ans;
		
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 965 ms 928 KB Output is correct
11 Correct 827 ms 928 KB Output is correct
12 Correct 389 ms 972 KB Output is correct
13 Correct 878 ms 936 KB Output is correct
14 Correct 721 ms 916 KB Output is correct
15 Correct 811 ms 1016 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 965 ms 928 KB Output is correct
11 Correct 827 ms 928 KB Output is correct
12 Correct 389 ms 972 KB Output is correct
13 Correct 878 ms 936 KB Output is correct
14 Correct 721 ms 916 KB Output is correct
15 Correct 811 ms 1016 KB Output is correct
16 Execution timed out 4075 ms 35476 KB Time limit exceeded
17 Halted 0 ms 0 KB -