oj.uz

Submission #1036636

# Submission time Handle Problem Language Result Execution time Memory
1036636 2024-07-27T15:04:35 Z MrAndria Easter Eggs (info1cup17_eastereggs) C++14
87 / 100
 11 ms 612 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
// static int N, X, cntQ;
// static vector < int > v[1009];
int timer=0,l,r,mid,ans;
pair <int,int> tin[1024];

vector <int> adj[1024],v1;
// int query (vector < int > h)
// {
//     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;
// }

void dfs(int x,int p){
    tin[x]=make_pair(timer++,x);
    for(auto u:adj[x]){
        if(u!=p){
            dfs(u,x);
        }
    }
}
int findEgg(int n,vector < pair <int,int> > bridges){
    timer=0;
    for(int i=1;i<=n;i++){
        adj[i].clear();
    }
    for(int i=0;i<=n-2;i++){
        adj[bridges[i].ff].pb(bridges[i].ss);
        adj[bridges[i].ss].pb(bridges[i].ff);
    }
    dfs(1,0);
    sort(tin+1,tin+n+1);
    // for(int i=1;i<=n;i++){
    //     cout<<tin[i].ff<<"----"<<tin[i].ss<<endl;
    // }
    l=1;
    r=n;
    while(l<=r){
        mid=(l+r)/2;
        v1.clear();
        for(int i=1;i<=mid;i++){
            v1.pb(tin[i].ss);
            // cout<<tin[i].ss<<" ";
        }
        // cout<<endl;
        if(query(v1)==1){
            ans=tin[mid].ss;
            r=mid-1;

        }else{
            l=mid+1;
        }

    }
    return ans;
}


// int main ()
// {
// //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;
// }

Subtask #1
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Number of queries: 5
2 Partially correct 1 ms 344 KB Number of queries: 5
3 Partially correct 1 ms 344 KB Number of queries: 5
4 Partially correct 0 ms 344 KB Number of queries: 5

Subtask #2
40.0 / 40.0

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

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 612 KB Number of queries: 10
2 Correct 10 ms 600 KB Number of queries: 9
3 Partially correct 9 ms 516 KB Number of queries: 10
4 Partially correct 9 ms 344 KB Number of queries: 10