oj.uz

Submission #623646

# Submission time Handle Problem Language Result Execution time Memory
623646 2022-08-06T08:16:07 Z l_reho Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 43940 KB 
#include <bits/stdc++.h>
#include "werewolf.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});
	
	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){
					if(visited[a][0]) continue;
					
					q.push({a, 0});
					visited[a][0] = true;
					continue;
				}
				
				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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -