Submission #624309

#	Time	Username	Problem	Language	Result	Execution time	Memory
624309		l_reho	Werewolf (IOI18_werewolf)	C++14	0 / 100	2479 ms	40440 KiB

werewolf

#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;
vector<int> V;
vector<int> MN, MX;

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 5 3
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

6 5 3
4 1
1 5
5 0
0 2
2 3 
2 0 1 2
4 2 2 2
5 4 3 4
*  
*/
 
void build(int p, int L, int R){
	
	if(L == R){
		MN[p] = V[L];
		MX[p] = V[L];
		
		return;
	}
	
	int mid = (L+R)/2;
	
	build(p*2, L, mid);
	build(p*2+1, mid+1, R);
	
	MN[p] = min(MN[p*2], MN[p*2+1]);
	MX[p] = max(MX[p*2], MX[p*2+1]);
	
}

int getMin(int p, int L, int R, int i, int j){
	
	if(i > R || j < L) return INT_MAX;
	
	if(i <= L && R <= j) return MN[p];
	
	int mid = (L+R)/2;
	
	return min(getMin(p*2, L, mid, i, j),getMin(p*2+1, mid+1, R, i, j));
	
}

int getMax(int p, int L, int R, int i, int j){
	
	if(i > R || j < L) return -1;
	
	if(i <= L && R <= j) return MX[p];
	
	int mid = (L+R)/2;
	
	return max(getMax(p*2, L, mid, i, j),getMax(p*2+1, mid+1, R, i, j));
	
}


 
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>());
	MN.assign(N*4+1, 0);
	MX.assign(N*4+1, 0);

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

	bool subtask3 = M == N-1;
	
	
	map<int, int> mp;
	for(int i = 0; i < N; i++)
		mp[graph[i].size()]++;
		
	subtask3 = mp[1] == 2 && mp[2] == N-2;
	
	if(subtask3){
		// costruisco la catena
		
		int root = 0;
		
		for(int i = 0; i < N; i++) if(graph[i].size() == 1){root = i; break;}
		
		int curr = root;	
		int prev = -1;
		
		vector<bool> visited(N, 0);
		
		while(curr != prev){
			visited[curr] = true;
			V.push_back(curr);
	
			int next = curr;
			
			for(int a : graph[curr]){
				if(visited[a]) continue;
				
				next = a;
				
			}
			
			prev = curr;
			curr = next;
		}
		
		// for(int x = 0; x < N; x++) cout<<V[x]<<" ";
		// cout<<endl;
		
		build(1, 0, N-1);
		
		map<int, int> mp;
		
		for(int x = 0; x < N; x++)
			mp[V[x]] = x;
		
		for(int i = 0; i < Q; i++){
			
			int idxS = mp[S[i]];
			int idxE = mp[E[i]];
			
			bool inv = idxS > idxE;
			
			if(idxS > idxE) swap(idxS, idxE); // da sistemare
			
			int low = idxS;
			int high = idxE;
			
			// cout<<"DEBUG-->"<<low<<" "<<high<<endl;
			
			while(low < high){
				int mid = low + (high-low)/2;
				
				if(!inv){
					int mnLeft = getMin(1, 0, N-1, idxS, mid), mxRight = getMax(1, 0, N-1, mid+1, idxE);	
					
					
					
					if(mnLeft >= L[i] && mxRight <= R[i]){
						// apposto NO!
						
						if(mid >= L[i] && mid <= R[i]){
							ans[i] = 1;
							break;
						}
						
						if(mid < L[i]){
							low = mid+1;
						}else if(mid > R[i]) high = mid;
												
					}else if(mnLeft < L[i]){
						high = mid;
						
					}else if(mxRight > R[i]){
						low = mid+1;
						
					}
				}else{
					
					int mxLeft = getMax(1, 0, N-1, idxS, mid), mnRight = getMin(1, 0, N-1, mid+1, idxE);	
					
					if(mnRight >= L[i] && mxLeft <= R[i]){
						
						if(mid >= L[i] && mid <= R[i]){
							ans[i] = 1;
							break;
						}
						
						if(mid < L[i]){
							high = mid;
						}else if(mid > R[i]) low = mid+1;
				
						
					}else if(mnRight < L[i]){
						low = mid+1;
						
					}else if(mxLeft > R[i]){
						high = mid;
						
					}
					
					
				}
				
			}
		
			
		}
		
		
		return ans;
	}
	
	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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51