oj.uz

Submission #476785

# Submission time Handle Problem Language Result Execution time Memory
476785 2021-09-28T14:00:47 Z lovrot Easter Eggs (info1cup17_eastereggs) C++11
100 / 100
 20 ms 456 KB 
#include <bits/stdc++.h> 
#include "grader.h"
#include<unistd.h>

#define X first
#define Y second

using namespace std; 

vector<int> g[1010];
vector<int> half;
vector<int> all; 
vector<int> help;
vector<int> dod;

int have;
bool took[1010];
bool nxt[1010];
bool need[1010];
bool cango[1010];

/*
int calc;
int egg;
bool wrong; 
*

int query(vector< int > v){ 
    int ap[1009];
    if (v.empty ()) return 0;
    memset(ap, 0, sizeof(ap));

    for (auto it = v.begin (); it != v.end (); it ++)
        ap[*it] = 1;

    queue < int > cc;
    cc.push (v[0]), ap[v[0]] = 2;

    while (!cc.empty ()){
        int nod = cc.front ();
        cc.pop ();
        for (auto it = g[nod].begin(); it != g[nod].end (); it ++)
            if (ap[*it] == 1)
                ap[*it] = 2, cc.push (*it);
    }

    for (int i : v)
        if (ap[i] == 1){ 
        	cout << "!!Something went wrong!!\n";
        	wrong = false;
        	return 0;
        }
    for (auto it = v.begin (); it != v.end (); it ++)
        if (*it == egg) return 1;
    return 0;
}
*/
bool dfs(int x, int last){ 
	bool out = need[x];

	for(int y : g[x]){ 
		if(y == last) continue;

		out |= dfs(y, x);
	}

	if(out){ 
		 all.push_back(x);
		 cango[x] = true;
	}

	return out;
}

void fix(){ 	
	dod.clear();
	memset(need, 0, sizeof(need));

	for(int x : all)
		need[x] = true;

	int start = all[0];

	all.clear(); 
	dfs(start, -1);

	//for(int x : dod)	
	//	all.push_back(x);
}

void findHalf(int x, int par){ 
	if(have == 0)
		return;

	if(took[x]){
		nxt[x] = true;
		have--;
	}

	half.push_back(x);

	for(int y : g[x]){ 
		if(y == par || !cango[y]) 
			continue;

		findHalf(y, x);
	}
} 

int findEgg (int N, vector< pair< int, int > > graf ){
	int on = N;

	//calc = 0;

	memset(took, 0, sizeof(took));
	all.clear(); 
	half.clear();
	help.clear();
	dod.clear();
	have = 0;
	memset(nxt, 0, sizeof(nxt));
	memset(need, 0, sizeof(need));

	for(int i = 0; i <= N; i++)
		g[i].clear();

	for(int i = 0; i < N - 1; i++){ 
		int x = graf[i].X;
		int y = graf[i].Y;

		g[x].push_back(y);
		g[y].push_back(x);
	
		if(!took[x]){ 
			all.push_back(x);
			took[x] = true; 
		}
		if(!took[y]){ 
		 	all.push_back(y);
		 	took[y] = true;
		}
	}

	int ret = 1;

	while(all.size() > 1){ 
		//calc++;

		memset(cango, false, sizeof(cango));

	//	for(int x : all)	cout << x << " ";

		fix();

	/*	cout << "\n";

		for(int x : all) cout << x << " "; 

		cout << "\n";

		for(int i = 1; i <= on; i++)
			cout << took[i] << " ";

		cout << "\n";

	*/	have = N / 2;
		
		half.clear();
		memset(nxt, false, sizeof(nxt));

		findHalf(all[0], -1);

	/*	cout << "half ";
		for(int x : half)	cout << x << " "; 
		cout << "\n";
	*/
		int ans = query(half);

	//	cout << "\n" << ans << " ans to the query\n";


	//	cout << "-----------------\n";
		if(ans == 1){ 
			N /= 2;
		}
		else{ 
			if(ans != 0){ 
				return 1;
			}
			N = N - N / 2;
		}

		help.clear();

		for(int x : all){ 
			if(took[x] and nxt[x] == ans) 
				help.push_back(x);
			else 
				took[x] = false;
		}
		all.clear();

		for(int x : help){ 
			//cout << x << " took to the nxt query\n";
			all.push_back(x);
		}
	}

	if(all.size())
		 ret = all[0];

	return ret;
}

/*
int main(){

	srand(time(0) * getpid());

	vector< pair<int, int> > edgs;

	int maxn = 512;

	wrong = true;

	int cnt = 0;
	while(wrong && cnt < 1000){
		cnt++;
		edgs.clear();

		int m = (rand() % maxn) + 1;
		cout << "N(nodes) = " << m << "\n";
		int x = (rand() % m) + 1;

		egg = x;
		cout << "Egg is on " << x << "th node\n";
			
		for(int j = 1; j <  m; j++){ 
			int y = (rand() % j) + 1;

			cout << j + 1 << ' ' << y << "\n";
			edgs.push_back({j + 1, y});
		}

		int ansp = findEgg(m, edgs);

		cout << "Program found egg on " << ansp << " node, after asking " << calc << " queries\n";
		cout << "Which is: ";
		if(ansp == x)
			cout << "true\n";
		else
			cout << "false\n";

		cout << "-------------\n";

	}
	cout << cnt << " of 1000";
	return 0;	

} */

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:111:6: warning: unused variable 'on' [-Wunused-variable]
  111 |  int on = N;
      |      ^~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Number of queries: 4
2 Correct 1 ms 200 KB Number of queries: 4
3 Correct 1 ms 200 KB Number of queries: 4
4 Correct 2 ms 200 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 328 KB Number of queries: 8
2 Correct 9 ms 328 KB Number of queries: 9
3 Correct 13 ms 328 KB Number of queries: 9
4 Correct 13 ms 328 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 328 KB Number of queries: 9
2 Correct 15 ms 328 KB Number of queries: 9
3 Correct 20 ms 456 KB Number of queries: 9
4 Correct 10 ms 328 KB Number of queries: 9