oj.uz

Submission #805986

# Submission time Handle Problem Language Result Execution time Memory
805986 2023-08-04T04:11:05 Z LIF Werewolf (IOI18_werewolf) C++14
49 / 100
 879 ms 72684 KB 
#include "werewolf.h"
#include<vector>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int pos[300005];
int ind[300005];
int id[300005];
int val[300005];
vector<int> ans;
vector<int> vv[300005];
int stmin[200005][23];
int stmax[200005][23];
bool flag1[400005];
bool vis[300005];
bool flag2[300005];
bool vis2[30005];
void dfs(int now,int num)
{
	//cout<<now<<" "<<num<<endl;
	vis[now] = true;
	id[now] = num;
	val[num] = now;
	for(int i=0;i<vv[now].size();i++)
	{
		int to = vv[now][i];
		if(vis[to] == false)dfs(to,num+1);
	}
	return;
}
int checkmin(int x,int y)
{
	int len = log(y-x+1) / log(2);
	return min(stmin[x][len],stmin[y-(1<<(len))+1][len]); 
}
int checkmax(int x,int y)
{
	int len = log(y-x+1) / log(2);
	return max(stmax[x][len],stmax[y-(1<<(len))+1][len]);
}
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)
{
	if(N <= 3000)
	{
		for(int i=0;i<X.size();i++)
		{
			vv[X[i]].push_back(Y[i]);
			vv[Y[i]].push_back(X[i]);
		}
		for(int i=0;i<S.size();i++)
		{	
			queue<int> q;
			for(int j=0;j<N;j++)flag1[j] = false;
			for(int j=0;j<N;j++)flag2[j] = false;
			for(int j=0;j<N;j++)vis[j] = false;
			for(int j=0;j<N;j++)vis2[j] = false;
			q.push(S[i]);
			flag1[S[i]] = true;
			while(q.empty() == false)
			{
				//cout<<"yeah"<<endl;
				int xx = q.front();
				q.pop();
				if(vis[xx] == true)continue;
				vis[xx] = true;
				for(int j=0;j<vv[xx].size();j++)
				{
					int to = vv[xx][j];
					if(to >= L[i])
					{
						flag1[to] = true;
					//	vis[to] = true;
						q.push(to);
					}
				}
			}
			//cout<<"YEAH"<<endl;
			q.push(E[i]);
			flag2 [E[i]] = true;
			while(q.empty() == false)
			{
				int xx = q.front();
				q.pop();
				//cout<<xx<<endl;
				if(vis2[xx] == true)continue;
				vis2[xx] = true;
				for(int j=0;j<vv[xx].size();j++)
				{
					int to = vv[xx][j];
					if(to <= R[i])
					{
						flag2[to] = true;
						q.push(to);
					}
				}
			}
			for(int j=0;j<N;j++)
			{
				if(flag1[j] == true && flag2[j] == true && L[i] <= j && j <= R[i])
				{
					ans.push_back(1);
					break;
				}
			}
			if(ans.size() < i+1)ans.push_back(0);
		}
		return ans;
	}
	else
	{
			for(int i=0;i<X.size();i++)
		{
			ind[X[i]]++;ind[Y[i]]++;
			vv[X[i]].push_back(Y[i]);
			vv[Y[i]].push_back(X[i]);
		}
		//cout<<"yeah"<<endl;
		for(int i=0;i<N;i++)
		{
			if(ind[i] != 1)continue;
			dfs(i,0);
			break;
		}
		for(int i=0;i<N;i++)
		{
			stmin[i][0] = val[i];
			stmax[i][0] = val[i];
		}
		for(int i=1;i<=20;i++)
		{
			for(int j=0;j+ (1<<i) - 1< N;j++)
			{
				stmin[j][i] = min(stmin[j][i-1],stmin[j+(1<<(i-1))][i-1]);
				stmax[j][i] = max(stmax[j][i-1],stmax[j+(1<<(i-1))][i-1]);
			}
		}
		/*for(int i=0;i<N;i++)cout<<i<<" ";
		cout<<endl;;
		for(int i=0;i<N;i++)cout<<id[i]<<" ";
		cout<<endl;
		for(int i=0;i<N;i++)cout<<val[i]<<" ";
		cout<<endl;*/
	//	cout<<checkmax(1,5)<<endl;
		for(int i=0;i<S.size();i++)
		{
			int xx = id[S[i]];
			int yy = id[E[i]];
			if(xx < yy)
			{
				int ll = xx;int rr = yy;
				int last1 = xx;
				int last2 = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmin(xx,mid) >= L[i])
					{
						last1 = mid;
						ll = mid + 1;
					}
					else rr = mid - 1;
				}
				ll = xx;rr = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmax(mid,yy) <= R[i])
					{
						last2 = mid;
						rr = mid - 1;
					}
					else ll = mid+1;
				}
				if(last1 >= last2)ans.push_back(1);
				else ans.push_back(0);
		//		cout<<last1<<" "<<last2<<endl;
			}
			else
			{
				swap(xx,yy);
				int ll = xx;int rr = yy;
				int last1 = xx;
				int last2 = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmax(xx,mid) <= R[i])
					{
						last1 = mid;
						ll = mid + 1;
					}
					else rr = mid - 1;
				}
				ll = xx;rr = yy;
				while(ll <= rr)
				{
					int mid = (ll+rr)>>1;
					if(checkmin(mid,yy) >= L[i])
					{
						last2 = mid;
						rr = mid - 1;
					}
					else ll = mid+1;
				}
				if(last1 >= last2)ans.push_back(1);
				else ans.push_back(0);
			}
		}
		return ans;	
	}
}

Compilation message

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0;i<vv[now].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:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<S.size();i++)
      |               ~^~~~~~~~~
werewolf.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=0;j<vv[xx].size();j++)
      |                 ~^~~~~~~~~~~~~~
werewolf.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int j=0;j<vv[xx].size();j++)
      |                 ~^~~~~~~~~~~~~~
werewolf.cpp:107:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |    if(ans.size() < i+1)ans.push_back(0);
      |       ~~~~~~~~~~~^~~~~
werewolf.cpp:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    for(int i=0;i<X.size();i++)
      |                ~^~~~~~~~~
werewolf.cpp:146:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int i=0;i<S.size();i++)
      |               ~^~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7272 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 249 ms 7636 KB Output is correct
11 Correct 156 ms 7624 KB Output is correct
12 Correct 22 ms 7640 KB Output is correct
13 Correct 277 ms 7636 KB Output is correct
14 Correct 177 ms 7640 KB Output is correct
15 Correct 209 ms 7724 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 72676 KB Output is correct
2 Correct 598 ms 72640 KB Output is correct
3 Correct 618 ms 72576 KB Output is correct
4 Correct 587 ms 72608 KB Output is correct
5 Correct 699 ms 72604 KB Output is correct
6 Correct 720 ms 72664 KB Output is correct
7 Correct 653 ms 72676 KB Output is correct
8 Correct 627 ms 72684 KB Output is correct
9 Correct 362 ms 72648 KB Output is correct
10 Correct 321 ms 72644 KB Output is correct
11 Correct 286 ms 72640 KB Output is correct
12 Correct 379 ms 72608 KB Output is correct
13 Correct 879 ms 72640 KB Output is correct
14 Correct 838 ms 72676 KB Output is correct
15 Correct 854 ms 72632 KB Output is correct
16 Correct 849 ms 72600 KB Output is correct
17 Correct 812 ms 72572 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 3 ms 7272 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 3 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 249 ms 7636 KB Output is correct
11 Correct 156 ms 7624 KB Output is correct
12 Correct 22 ms 7640 KB Output is correct
13 Correct 277 ms 7636 KB Output is correct
14 Correct 177 ms 7640 KB Output is correct
15 Correct 209 ms 7724 KB Output is correct
16 Correct 690 ms 72676 KB Output is correct
17 Correct 598 ms 72640 KB Output is correct
18 Correct 618 ms 72576 KB Output is correct
19 Correct 587 ms 72608 KB Output is correct
20 Correct 699 ms 72604 KB Output is correct
21 Correct 720 ms 72664 KB Output is correct
22 Correct 653 ms 72676 KB Output is correct
23 Correct 627 ms 72684 KB Output is correct
24 Correct 362 ms 72648 KB Output is correct
25 Correct 321 ms 72644 KB Output is correct
26 Correct 286 ms 72640 KB Output is correct
27 Correct 379 ms 72608 KB Output is correct
28 Correct 879 ms 72640 KB Output is correct
29 Correct 838 ms 72676 KB Output is correct
30 Correct 854 ms 72632 KB Output is correct
31 Correct 849 ms 72600 KB Output is correct
32 Correct 812 ms 72572 KB Output is correct
33 Incorrect 282 ms 71044 KB Output isn't correct
34 Halted 0 ms 0 KB -