oj.uz

Submission #895625

# Submission time Handle Problem Language Result Execution time Memory
895625 2023-12-30T12:00:21 Z maxFedorchuk Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 17 ms 488 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const long long MX=600;

vector < int > mas[MX];

int pos1[MX];
int pos2[MX];
/*
int query(vector < int > islands)
{
    for(auto u:islands)
    {
        cout<<u<<" ";
    }
    cout<<"\n";

    int ans;
    cin>>ans;

    return ans;
}
*/
vector < int > chk(int k1,int n)
{
    for(int i=1;i<=n;i++)
    {
        pos2[i]=0;
    }

    queue < int > q;
    q.push(1);

    int zlk1=k1;

    while(zlk1!=0)
    {
        if(q.empty())
        {
            while(true)
            {
                zlk1=1;
            }
        }

        int zar=q.front();
        q.pop();

        pos2[zar]=1;
        zlk1-=pos1[zar];

        for(auto vr:mas[zar])
        {
            if(!pos2[vr])
            {
                q.push(vr);
            }
        }
    }

    vector < int > zap;
    for(int i=1;i<=n;i++)
    {
        if(pos2[i])
        {
            zap.push_back(i);
        }
    }

    return zap;
}
int findEgg(int n, vector < pair < int, int > > bridges)
{
    for(int i=1;i<=n;i++)
    {
        pos1[i]=1;
        mas[i].clear();
    }

    for(auto [a,b]:bridges)
    {
        mas[a].push_back(b);
        mas[b].push_back(a);
    }

    int k1=n;

    while(k1!=1)
    {
        int nwk1=k1/2;

        if(query(chk(nwk1,n)))
        {
            for(int i=1;i<=n;i++)
            {
                if(pos1[i] && pos2[i])
                {
                    pos1[i]=1;
                }
                else
                {
                    pos1[i]=0;
                }
            }

            k1=nwk1;
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(pos1[i] && !pos2[i])
                {
                    pos1[i]=1;
                }
                else
                {
                    pos1[i]=0;
                }
            }

            k1-=nwk1;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(pos1[i]==1)
        {
            return i;
        }
    }

    while(true)
    {
        k1=0;
    }

    return 0;
}
/*
int main()
{
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);

    int n=5;

    vector < pair < int , int > > bridges(n-1);
    bridges[0]=make_pair(1,2);
    bridges[1]=make_pair(1,3);
    bridges[2]=make_pair(2,4);
    bridges[3]=make_pair(4,5);

    cout<<findEgg(n,bridges)<<"\n";
    return 0;
}
*/

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for(auto [a,b]:bridges)
      |              ^

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 344 KB Number of queries: 9
2 Correct 11 ms 344 KB Number of queries: 9
3 Correct 11 ms 344 KB Number of queries: 9
4 Correct 13 ms 488 KB Number of queries: 9