Submission #522016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522016	2022-02-03T15:33:34 Z	iskhakkutbilim	Easter Eggs (info1cup17_eastereggs)	C++14	Compilation error	0 ms	0 KB

eastereggs

#include<bits/stdc++.h>
// #include "grader.h"

using namespace std;

 int N, X, cntQ;
 vector < int > v[1009];


int query (vector < int > h)
{
	// cout << 't';
    cntQ ++;
    int ap[1009];
    if (h.empty ()) return 0;
    for (int i=1; i<=N; i++)
        ap[i] = 0;
    for (auto it = h.begin (); it != h.end (); it ++)
        ap[*it] = 1;
    queue < int > cc;
    cc.push (h[0]), ap[h[0]] = 2;
    while (!cc.empty ())
    {
        int nod = cc.front ();
        cc.pop ();
        for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
            if (ap[*it] == 1)
                ap[*it] = 2, cc.push (*it);
    }
    for (int i=1; i<=N; i++)
        if (ap[i] == 1) return -1;
    for (auto it = h.begin (); it != h.end (); it ++)
        if (*it == X) return 1;
    return 0;
}



int findEgg (int N, vector < pair < int, int > > bridges)
{
	vector<int> g[N+1];
	vector<int> used(N +1, 0);
	vector<int> island;
	queue<int> q;
	for(int i = 0;i < N-1; i++){
		int a = bridges[i].first;
		int b = bridges[i].second;
		g[a].push_back(b);
		g[b].push_back(a);
	}
   	q.push(1);
   	used[1] = 1;
   	island.push_back(1);
   	while(!q.empty()){
   		int v = q.front();
   		q.pop();
   		island.push_back(v);	
   		for(auto to : g[v]){
   			if(used[to] == 0){
   				used[to] = 1;
   				q.push(to);
   			}		
   		}
   	}
   	// for(auto x : qu){
		// cout << x << " ";
	// }
	// cout << "\n";
//    	
	int l = 0, r = island.size()-1;
	while(r > l){
		int m = (l + r) / 2;
		vector<int> st;
		for(int i = 0;i <= m; i++){
			st.push_back(island[i]);
		}
		if(query(st)==1){
			r = m;
		}else l = m + 1;
	}
   	return island[l];
}

int main ()
{
// freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
int Queries;
vector < pair < int, int > > param;
for (int i=1; i<N; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    v[x].push_back (y);
    v[y].push_back (x);
    param.push_back ({x, y});
}
scanf ("%d", &Queries);
while (Queries --)
{
    scanf ("%d", &X), cntQ = 0;
    int Y = findEgg (N, param);
    if (X != Y)
    {
        printf ("WA %d instead of %d\n", Y, X);
        return 0;
    }
    printf ("OK %d\n", cntQ);
}
return 0;
}

Compilation message

eastereggs.cpp: In function 'int main()':
eastereggs.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 | scanf ("%d", &N);
      | ~~~~~~^~~~~~~~~~
eastereggs.cpp:95:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf ("%d %d", &x, &y);
      |     ~~~~~~^~~~~~~~~~~~~~~~~
eastereggs.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 | scanf ("%d", &Queries);
      | ~~~~~~^~~~~~~~~~~~~~~~
eastereggs.cpp:103:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf ("%d", &X), cntQ = 0;
      |     ~~~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/cc35IZbE.o: in function `query(std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x0): multiple definition of `query(std::vector<int, std::allocator<int> >)'; /tmp/ccfplaGF.o:eastereggs.cpp:(.text+0x50): first defined here
/usr/bin/ld: /tmp/cc35IZbE.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfplaGF.o:eastereggs.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status