oj.uz

Submission #243013

# Submission time Handle Problem Language Result Execution time Memory
243013 2020-06-30T07:31:03 Z nnnnnnnnnnnnnnnn Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 26 ms 384 KB 
#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
int n,cnt,mid;
vector<vi> graph;
vi node;
vi no,yes;
void dfs(int start,int pa)
{
	int i,j;
	if(cnt==mid)		return;
	node.push_back(start);
	if(no[start])	++cnt;
	for(i=0;i<graph[start].size();++i)
	{
		j = graph[start][i];
		if(j!=pa)
		{
			dfs(j,start);
		}
	}
}
int findEgg(int n,vector<ii> edge)
{
	int i,j;
	graph.assign(n+1,vi());
	no.assign(n+1,1);
	yes.assign(n+1,-1);
	for(i=0;i<edge.size();++i)
	{
		graph[edge[i].first].push_back(edge[i].second);
		graph[edge[i].second].push_back(edge[i].first);
	}
	int curr = n;
	while(curr!=1)
	{
		node.clear();
		mid = (curr+1)/2;
		cnt = 0;
		dfs(1,1);
		if(query(node)==false)
		{
			for(i=0;i<node.size();++i)
			{
				no[node[i]] = 0;
			}
			curr -= mid;
		}
		else
		{
			yes.assign(n+1,0);
			for(i=0;i<node.size();++i)
			{
				yes[node[i]] = no[node[i]];
			}
			for(i=1;i<=n;++i)	no[i]=yes[i];
			curr = mid;
		}
	}
	for(i=1;i<=n;++i)	
	{
		if(no[i])
		{
			return i;
		}
	}
}

Compilation message

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:17:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<graph[start].size();++i)
          ~^~~~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:32:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<edge.size();++i)
          ~^~~~~~~~~~~~
eastereggs.cpp:46:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<node.size();++i)
            ~^~~~~~~~~~~~
eastereggs.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<node.size();++i)
            ~^~~~~~~~~~~~
eastereggs.cpp:28:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
eastereggs.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Number of queries: 4
2 Correct 5 ms 384 KB Number of queries: 4
3 Correct 6 ms 384 KB Number of queries: 4
4 Correct 6 ms 256 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 384 KB Number of queries: 8
2 Correct 19 ms 384 KB Number of queries: 9
3 Correct 25 ms 384 KB Number of queries: 9
4 Correct 23 ms 384 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 384 KB Number of queries: 9
2 Correct 22 ms 384 KB Number of queries: 9
3 Correct 24 ms 384 KB Number of queries: 9
4 Correct 23 ms 384 KB Number of queries: 9