제출 #332515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332515		pggp	늑대인간 (IOI18_werewolf)	C++14	49 / 100	956 ms	70628 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

//vector < bool > used_wer;
//vector < bool > used_hum;
vector < vector < int > > Ed;

int cur_R, cur_L;
int n, quests;

vector < int > A;
vector < int > A_rev;
vector < int > B;
vector < int > forw[22];
vector < int > back[22];
// forw – maksimum z przodu
// back – minimum z tyłu

bool db = false;


vector < int > s, e, l, r;

vector < bool > used_wer;
vector < bool > used_hum;
 
 
void wer_dfs(int vertex){
	used_wer[vertex] = true;
	for(int v : Ed[vertex]){
		if(!used_wer[v] and v <= cur_R){
			wer_dfs(v);
		}
	}
}
 
void hum_dfs(int vertex){
	used_hum[vertex] = true;
	for(int v : Ed[vertex]){
		if(!used_hum[v] and v >= cur_L){
			hum_dfs(v);
		}
	}
 
}
 
vector < int > check_validity2(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
	vector < int > ans;
	int Q = E.size();
	Ed.resize(N);
	used_wer.resize(N);
	used_hum.resize(N);
	for (int i = 0; i < X.size(); ++i)
	{
		Ed[X[i]].push_back(Y[i]);
		Ed[Y[i]].push_back(X[i]);
	}
 
 
 
	for(int q = 0; q < Q; q++){
		cur_R = R[q];
		cur_L = L[q];
		for (int i = 0; i < N; ++i)
		{
			used_hum[i] = false;
			used_wer[i] = false;
		}
		hum_dfs(S[q]);
		wer_dfs(E[q]);
		int to_return = 0;
		for (int i = 0; i < N; ++i)
		{
			if(used_hum[i] and used_wer[i]){
				to_return = 1;
			}
		}
		ans.push_back(to_return);
	}
	return ans;
}

// przy bound nierówność ostra
int forw_max(int start, int bound){
	int ans = 0;
	int exp = 0;
	int power = 1;
	while(exp < 22 and forw[exp][start] >= bound){
		exp++;
		power *= 2;
	}
	if(exp > 21){
		return power;
	}

	ans = power/2;

	//if(db)	cout << "ans = " << ans << endl;

	while(power > 1){
		exp--;
		power /= 2;
		if(forw[exp][start + ans] >= bound){
			//if(db)	cout << "power: " << power  << "exp: " << exp << endl;
			ans += power;
			if(start + ans >= n){
				return n;
			}
		}
	}
	return ans;
}


int back_min(int start, int bound){
	int ans = 0;
	int exp = 0;
	int power = 1;
	while(exp < 22 and back[exp][start] <= bound){
		exp++;
		power *= 2;
	}
	if(exp > 21){
		return n - 1;
	}

	ans = power/2;

	if(db)	cout << "ans = " << ans << endl;

	while(power > 1){
		exp--;
		power /= 2;
		if(back[exp][start - ans] <= bound){
			if(db)	cout << "power: " << power  << "exp: " << exp << endl;
			ans += power;
			if(start - ans <= 0){
				return n;
			}
		}
	}
	return ans;
}

vector < bool > check(){
	vector < bool > ans;
	for (int i = 0; i < 22; ++i)
	{
		forw[i].clear();
		forw[i].resize(n);
		back[i].clear();
		back[i].resize(n);
	}
	



	int power = 1;
	for (int i = 0; i < 22; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if(power == 1){
				if(j == n){
					forw[0][j] = A[n - 1];
				}
				else{
					forw[i][j] = A[j + 1];
				}
				
			}
			else{
				if(j + power / 2 < n){
					forw[i][j] = min(forw[i - 1][j], forw[i - 1][j + power / 2]);
				}
				else{
					forw[i][j] = forw[i - 1][j];
				}
			}
		}
		power *= 2;
	}

	

	power = 1;
	for (int i = 0; i < 22; ++i)
	{
		for(int j = 0; j < power and j < n and i > 0; j++){

			back[i][j] = back[i - 1][j];
		}
		for (int j = power / 2; j < n; ++j)
		{
			if(power == 1){
				if(j != 0){
					back[i][j] = A[j - 1];
				}
				else{
					back[i][j] = A[0];
				}
			}
			else{
				back[i][j] = max( back[i - 1][j], back[i - 1][j - power / 2]);
			}
		}
		power *= 2;
	}

if(db){
	for (int i = 0; i < n; ++i)
	{
		cout << i << ": ";
		for (int p = 0; p < 5; ++p)
		{
			cout << back[p][i] << " ";
		}
		cout << endl;
	}
	cout << endl;
	}




	for(int q = 0; q < quests; q++){
		int pos_s = A_rev[s[q]];
		int pos_e = A_rev[e[q]];
		int a = forw_max(pos_s, l[q]);
		int b = back_min(pos_e, r[q]);
		
		if(db){
			cout << "a = " << a << "; b = " << b << endl;
			cout << "L = " << l[q] << "; r = " << r[q] << endl;
			cout << "A[pos_s + a + 1]= " << A[pos_s + a + 1] << "; A[pos_e - b - 1] = " << A[pos_e - b - 1] << endl;
			cout << "pos_s = " << pos_s << "; pos_e = " << pos_e << endl << endl;
			cout << "A[pos_s] = " << A[pos_s] << "; A[pos_e] = " << A[pos_e] << endl << endl;
		}

		if(pos_s > pos_e){
			ans.push_back(false);
		}
		else{
			if(a + b >= pos_e - pos_s or pos_s == pos_e){
				ans.push_back(true);
			}
			else{
				ans.push_back(false);
			}
		}
		
	}
	

	return ans;
}

vector < int > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
	if(N <= 3000 and S.size() <= 3000){
		return check_validity2(N, X, Y, S, E, L, R);
	}
	vector < int > ans;
	int Q = E.size();
	quests = Q;
	Ed.resize(N);
	vector< int > emp;
	s = S;
	S=emp;
	e = E;
	E = emp;
	l = L;
	L = emp;
	r = R;
	R=emp;
	n = N;
	//used_wer.resize(N);
	//used_hum.resize(N);
	for (int i = 0; i < X.size(); ++i)
	{
		Ed[X[i]].push_back(Y[i]);
		Ed[Y[i]].push_back(X[i]);
	}


	A.resize(N);
	A_rev.resize(N);
	B.resize(N);
	for (int i = 0; i < N; ++i)
	{
		if(Ed[i].size() == 1){
			A[0] = i;
			int prev = i;
			int cur = Ed[i][0];
			int cur_ind = 1;
			while(Ed[cur].size() > 1){
				if(Ed[cur][0] != prev){
					prev = cur;
					A[cur_ind] = cur;
					cur = Ed[cur][0];
					cur_ind++;
				}
				else{
					prev = cur;
					A[cur_ind] = cur;
					cur = Ed[cur][1];
					cur_ind++;
				}
			}
			A[N - 1] = cur;
		}
	}

	for (int i = 0; i < N; ++i)
	{
		A_rev[A[i]] = i;
	}

	/*cout << "A: " << endl;
	for (int i = 0; i < N; ++i)
	{
		cout << A[i] << " ";
	}
	cout << endl <<  "A_rev: " << endl;
	for (int i = 0; i < N; ++i)
	{
		cout << A_rev[i] << " ";
	}
	cout << endl;*/


	

	vector < bool > a = check();
	B = A;
	for (int i = 0; i < A.size(); ++i)
	{
		A[i] = B[N - 1 - i];
		A_rev[A[i]] = i; 
	}
	vector < bool > b = check();

	for (int i = 0; i < a.size(); ++i)
	{
		ans.push_back(a[i] or b[i]);
	}
		
		//ans.push_back(to_return);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In function 'std::vector<int> check_validity2(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for (int i = 0; i < X.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:279:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |  for (int i = 0; i < X.size(); ++i)
      |                  ~~^~~~~~~~~~
werewolf.cpp:336:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  336 |  for (int i = 0; i < A.size(); ++i)
      |                  ~~^~~~~~~~~~
werewolf.cpp:343:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  343 |  for (int i = 0; i < a.size(); ++i)
      |                  ~~^~~~~~~~~~

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