oj.uz

Submission #805922

# Submission time Handle Problem Language Result Execution time Memory
805922 2023-08-04T02:24:43 Z LIF Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 32256 KB 
#include "werewolf.h"
#include<vector>
#include<bits/stdc++.h>
#include<queue>
using namespace std;
vector<int> vv[300005];
bool flag1[400005];
bool vis[300005];
bool flag2[300005];
bool vis2[30005];
vector<int> ans;
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++)
	{
		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;
  /*int Q = S.size();
  std::vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    A[i] = 0;
  }
  return A;*/
}

Compilation message

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:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<X.size();i++)
      |              ~^~~~~~~~~
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<S.size();i++)
      |              ~^~~~~~~~~
werewolf.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int j=0;j<vv[xx].size();j++)
      |                ~^~~~~~~~~~~~~~
werewolf.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int j=0;j<vv[xx].size();j++)
      |                ~^~~~~~~~~~~~~~
werewolf.cpp:76:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |   if(ans.size() < i+1)ans.push_back(0);
      |      ~~~~~~~~~~~^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7272 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7352 KB Output is correct
9 Correct 4 ms 7356 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 4 ms 7272 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7352 KB Output is correct
9 Correct 4 ms 7356 KB Output is correct
10 Correct 237 ms 7716 KB Output is correct
11 Correct 159 ms 7724 KB Output is correct
12 Correct 18 ms 7764 KB Output is correct
13 Correct 260 ms 7840 KB Output is correct
14 Correct 180 ms 7712 KB Output is correct
15 Correct 208 ms 7856 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 32256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7272 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7364 KB Output is correct
7 Correct 5 ms 7380 KB Output is correct
8 Correct 4 ms 7352 KB Output is correct
9 Correct 4 ms 7356 KB Output is correct
10 Correct 237 ms 7716 KB Output is correct
11 Correct 159 ms 7724 KB Output is correct
12 Correct 18 ms 7764 KB Output is correct
13 Correct 260 ms 7840 KB Output is correct
14 Correct 180 ms 7712 KB Output is correct
15 Correct 208 ms 7856 KB Output is correct
16 Execution timed out 4072 ms 32256 KB Time limit exceeded
17 Halted 0 ms 0 KB -