oj.uz

Submission #332514

# Submission time Handle Problem Language Result Execution time Memory
332514 2020-12-02T18:21:58 Z pggp Werewolf (IOI18_werewolf) C++14
41 / 100
 977 ms 62216 KB 
#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;
}

Compilation message

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.0 / 7.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 6 ms 1260 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 62004 KB Output is correct
2 Correct 948 ms 62088 KB Output is correct
3 Correct 917 ms 62088 KB Output is correct
4 Correct 854 ms 62088 KB Output is correct
5 Correct 831 ms 62200 KB Output is correct
6 Correct 693 ms 61960 KB Output is correct
7 Correct 837 ms 62216 KB Output is correct
8 Correct 841 ms 62088 KB Output is correct
9 Correct 508 ms 61960 KB Output is correct
10 Correct 483 ms 61960 KB Output is correct
11 Correct 507 ms 62088 KB Output is correct
12 Correct 484 ms 62092 KB Output is correct
13 Correct 977 ms 62120 KB Output is correct
14 Correct 957 ms 61960 KB Output is correct
15 Correct 974 ms 62088 KB Output is correct
16 Correct 970 ms 62088 KB Output is correct
17 Correct 832 ms 62088 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 6 ms 1260 KB Output isn't correct
11 Halted 0 ms 0 KB -