oj.uz

Submission #46270

# Submission time Handle Problem Language Result Execution time Memory
46270 2018-04-18T13:19:18 Z hiddentesla Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 67 ms 936 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<vector<int>> adj;
int findEgg (int n, vector < pair < int, int > > bridges)
{
    adj.resize(n+1);
    int temp,temp2;
    for(temp=0;temp<bridges.size();temp++)
    {
    	int x=bridges[temp].first,y=bridges[temp].second;
    	adj[x].push_back(y);
    	adj[y].push_back(x);
	}
	bool cntbisa[n+1]; int sisacnt=n;
	memset(cntbisa,true,sizeof(cntbisa));
	while(sisacnt>1)
	{
		//cout<<sisacnt<<"\n";
		queue<int> q;
		bool visited[n+1]; memset(visited,false,sizeof(visited));
		q.push(1);
		vector<int> stk;
		int udh=0;
		while(!q.empty())
		{
			int pos=q.front();
			q.pop();
			if(visited[pos])	continue;
			visited[pos]=true;
			stk.push_back(pos);
			if(cntbisa[pos])	udh++;
			if(udh>=(sisacnt+1)/2)
			{
				break;
			}
			for(temp=0;temp<adj[pos].size();temp++)
			{
				int thenode=adj[pos][temp];
				q.push(thenode);
			}
		}
		int lol=query(stk);
		//for(temp=0;temp<stk.size();temp++)	cout<<stk[temp]<<" "; cout<<"jawaban "<<lol<<"\n";
		//char c;
		 //cin>>c;
		if(lol==1)
		{
			sisacnt=udh;
			vector<int> yangval;
			for(temp=0;temp<stk.size();temp++)	if(cntbisa[stk[temp]])	yangval.push_back(stk[temp]);
			stk=yangval;
			memset(cntbisa,0,sizeof(cntbisa));
			for(temp=0;temp<stk.size();temp++)	cntbisa[stk[temp]]=true;
		}
		else
		{
			sisacnt-=udh;
			for(temp=0;temp<stk.size();temp++)	cntbisa[stk[temp]]=false;
		}	
		//cout<<"sisa mungkin = "; for(temp=1;temp<=n;temp++)	
	}
	for(temp=1;temp<=n;temp++)	if(cntbisa[temp])	return temp;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:9:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(temp=0;temp<bridges.size();temp++)
                ~~~~^~~~~~~~~~~~~~~
eastereggs.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(temp=0;temp<adj[pos].size();temp++)
               ~~~~^~~~~~~~~~~~~~~~
eastereggs.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(temp=0;temp<stk.size();temp++) if(cntbisa[stk[temp]]) yangval.push_back(stk[temp]);
               ~~~~^~~~~~~~~~~
eastereggs.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(temp=0;temp<stk.size();temp++) cntbisa[stk[temp]]=true;
               ~~~~^~~~~~~~~~~
eastereggs.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(temp=0;temp<stk.size();temp++) cntbisa[stk[temp]]=false;
               ~~~~^~~~~~~~~~~
eastereggs.cpp:8:14: warning: unused variable 'temp2' [-Wunused-variable]
     int temp,temp2;
              ^~~~~
eastereggs.cpp:64: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 3 ms 252 KB Number of queries: 4
2 Correct 3 ms 384 KB Number of queries: 4
3 Correct 2 ms 512 KB Number of queries: 4
4 Correct 2 ms 512 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 524 KB Number of queries: 8
2 Correct 35 ms 768 KB Number of queries: 9
3 Correct 66 ms 828 KB Number of queries: 9
4 Correct 58 ms 916 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 916 KB Number of queries: 9
2 Correct 55 ms 916 KB Number of queries: 9
3 Correct 52 ms 916 KB Number of queries: 9
4 Correct 67 ms 936 KB Number of queries: 9