oj.uz

Submission #1069852

# Submission time Handle Problem Language Result Execution time Memory
1069852 2024-08-22T09:23:50 Z Ice_man Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 20 ms 24152 KB 
/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>

#include "grader.h"

#define maxn 1000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double pd;

vector <int> v[maxn];

vector <int> tour;
void gen(int node , int par)
{
    tour.pb(node);
    for(auto& e : v[node])
    {
        if(e == par)
            continue;
        gen(e , node);
    }
}

vector <int> pom;
bool check(int x)
{
    pom.clear();
    for(int i = 0; i <= x; i++)
        pom.pb(tour[i]);
    return query(pom);
}

int n;
int findEgg(int N , vector <pii> bridges)
{
    for(int i = 1; i <= n; i++)
        v[i].clear();
    tour.clear();

    n = N;

    for(auto& e : bridges)
    {
        v[e.X].pb(e.Y);
        v[e.Y].pb(e.X);
    }

    gen(1 , -1);

    int l = 0 , r = tour.size() - 1;
    int mid;
    while(r > l)
    {
        mid = (l + r) / 2;
        if(check(mid) == true)
            r = mid;
        else
            l = mid + 1;
    }

    return tour[l];
}







/**int main()
{

    #ifdef ONLINE_JUDGE /// promeni
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    return 0;
}*/

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23896 KB Number of queries: 8
2 Correct 12 ms 23972 KB Number of queries: 9
3 Correct 20 ms 23956 KB Number of queries: 9
4 Correct 14 ms 23896 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23980 KB Number of queries: 9
2 Correct 14 ms 24152 KB Number of queries: 9
3 Correct 16 ms 23968 KB Number of queries: 9
4 Correct 14 ms 23976 KB Number of queries: 9