oj.uz

Submission #805979

# Submission time Handle Problem Language Result Execution time Memory
805979 2023-08-04T04:08:11 Z LIF Werewolf (IOI18_werewolf) C++14
34 / 100
 692 ms 81088 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 vis[300005];
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)
{
	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:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  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:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<X.size();i++)
      |              ~^~~~~~~~~
werewolf.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;i<S.size();i++)
      |              ~^~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 72696 KB Output is correct
2 Correct 577 ms 81000 KB Output is correct
3 Correct 537 ms 81064 KB Output is correct
4 Correct 573 ms 81044 KB Output is correct
5 Correct 580 ms 81064 KB Output is correct
6 Correct 585 ms 81048 KB Output is correct
7 Correct 561 ms 81040 KB Output is correct
8 Correct 510 ms 81060 KB Output is correct
9 Correct 385 ms 81088 KB Output is correct
10 Correct 286 ms 81004 KB Output is correct
11 Correct 299 ms 81040 KB Output is correct
12 Correct 336 ms 81088 KB Output is correct
13 Correct 692 ms 81044 KB Output is correct
14 Correct 606 ms 81012 KB Output is correct
15 Correct 623 ms 80992 KB Output is correct
16 Correct 640 ms 80976 KB Output is correct
17 Correct 571 ms 81084 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -