Submission #430738

#	Time	Username	Problem	Language	Result	Execution time	Memory
430738		albertolg101	Werewolf (IOI18_werewolf)	C++17	0 / 100	925 ms	97268 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
	
using namespace std;
using pii = pair<int, int>;
	
vector<int> is_a_graph (int n, vector<vector<int>> &g,
								std::vector<int> S, std::vector<int> E,
								std::vector<int> L, std::vector<int> R) {
	
	int Q = L.size(), m = g.size();
	vector<int> ans;
	
	vector<vector<int>> dp;
	vector<vector<bool>> flag;
	
	function<bool(int, int, int, int, int)> dfs = [&](int nod, bool race, int target, int l, int r)
	{
		if(flag[nod][race])
			return dp[nod][race];
	
		flag[nod][race] = true;
		if(!race and l <= nod and nod <= r)
			dp[nod][race] = dfs(nod, true, target, l, r);
	
		if(nod == target)
			return (dp[nod][race] | race);
	
		for(auto i: g[nod])
		{
			if(!race and l <= i)
				dp[nod][race] |= dfs(i, race, target, l, r); 
			
			if(race and i <= r)
				dp[nod][race] |= dfs(i, race, target, l, r);
		}
	
		return dp[nod][race];
	};
	
	for(int i = 0 ; i < Q ; i++)
	{
		dp = vector<vector<int>> (n, vector<int> (2, 0));
		flag = vector<vector<bool>> (n, vector<bool> (2, false));
		ans.push_back(dfs(S[i], false, E[i], L[i], R[i]));
	}
	
	return ans;
}
	
vector<int> is_a_line (int n, vector<vector<int>> g,
								std::vector<int> S, std::vector<int> E,
								std::vector<int> L, std::vector<int> R) {
	
	int Q = L.size();
	vector<int> cc(n), ans;
	
	function<void(int, int)> dfs = [&](int nod, int father)
	{
		for(auto i: g[nod])
		{
			if(i != father)
			{
				cc[i] = cc[nod] + 1;
				dfs(i, nod);
			}
		}
	};
	
	for(int i = 0 ; i < n ; i++)
	{
		if(g[i].size() == 1)
		{
			dfs(i, -1);
			break;
		}
	}
	
	vector<int> rcc(n);
	
	for(int i = 0 ; i < n ; i++)
		rcc[cc[i]] = i;
	
	vector<vector<int>> rminq(n, vector<int> (18)), rmaxq = rminq;
	
	for(int i = 0 ; i < cc.size() ; i++)
	{
		rminq[i][0] = cc[i];
		rmaxq[i][0] = cc[i];
	}
	
	for(int i = 1 ; (1<<i) < n ; i++)
	{
		for(int j = 0 ; j + (1<<i) - 1 < n ; j++)
		{
			rminq[j][i] = min(rminq[j][i-1], rminq[j+(1<<(i-1))][i-1]);
			rmaxq[j][i] = max(rmaxq[j][i-1], rmaxq[j+(1<<(i-1))][i-1]);
		}
	}
	
	function<pii(int, int)> query = [&](int l, int r)
	{
		int lg = __lg(r-l+1);
		return (pii){
			min(rminq[l][lg], rminq[r-(1<<lg)+1][lg]),
			max(rmaxq[l][lg], rmaxq[r-(1<<lg)+1][lg])
		};
	};
	
	for(int i = 0 ; i < Q ; i++)
	{
		int s = rcc[S[i]], e = rcc[E[i]], l = L[i], r = R[i];
	
		bool sol = (e < s);
		if(e < s)
			swap(s, e);
	
		for(int i = 18 ; i >= 0 ; i--)
		{
			int target = s + (1<<i);
	
			if(target > e)
				continue;
	
			if(!sol and l <= query(s+1, target).first)
				s = target;
			
			if(sol and query(s+1, target).second <= r)
				s = target;
		}
	
		if(!sol)
			ans.push_back(query(s, e).second <= r);
	
		else
			ans.push_back(l <= query(s, e).first);
	
		cout << ans.back() << endl ;
	}
	
	return ans ;
}
	
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 Q = L.size(), m = X.size(), maxDegree = 0;
	vector<int> ans;
	vector<vector<int>> g(n);
	
	for(int i = 0 ; i < m ; i++)
	{
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	
		maxDegree = max({
			maxDegree, 
			(int)g[X[i]].size(), 
			(int)g[Y[i]].size()
		});
	}
	
	if(maxDegree > 2)
		return is_a_graph(n, g, S, E, L, R);
	
	else
		return is_a_line(n, g, S, E, L, R);
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> is_a_graph(int, std::vector<std::vector<int> >&, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:11:20: warning: unused variable 'm' [-Wunused-variable]
   11 |  int Q = L.size(), m = g.size();
      |                    ^
werewolf.cpp: In function 'std::vector<int> is_a_line(int, std::vector<std::vector<int> >, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i = 0 ; i < cc.size() ; i++)
      |                  ~~^~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:148:6: warning: unused variable 'Q' [-Wunused-variable]
  148 |  int Q = L.size(), m = X.size(), maxDegree = 0;
      |      ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51