oj.uz

Submission #477969

# Submission time Handle Problem Language Result Execution time Memory
477969 2021-10-04T20:23:02 Z omohamadooo Easter Eggs (info1cup17_eastereggs) C++14
81 / 100
 45 ms 7428 KB 
/*
      ___           ___           ___           ___           ___           ___           ___          _____          ___           ___           ___
     /  /\         /__/\         /  /\         /__/\         /  /\         /__/\         /  /\        /  /::\        /  /\         /  /\         /  /\
    /  /::\       |  |::\       /  /::\        \  \:\       /  /::\       |  |::\       /  /::\      /  /:/\:\      /  /::\       /  /::\       /  /::\
   /  /:/\:\      |  |:|:\     /  /:/\:\        \__\:\     /  /:/\:\      |  |:|:\     /  /:/\:\    /  /:/  \:\    /  /:/\:\     /  /:/\:\     /  /:/\:\
  /  /:/  \:\   __|__|:|\:\   /  /:/  \:\   ___ /  /::\   /  /:/~/::\   __|__|:|\:\   /  /:/~/::\  /__/:/ \__\:|  /  /:/  \:\   /  /:/  \:\   /  /:/  \:\
 /__/:/ \__\:\ /__/::::| \:\ /__/:/ \__\:\ /__/\  /:/\:\ /__/:/ /:/\:\ /__/::::| \:\ /__/:/ /:/\:\ \  \:\ /  /:/ /__/:/ \__\:\ /__/:/ \__\:\ /__/:/ \__\:\
 \  \:\ /  /:/ \  \:\~~\__\/ \  \:\ /  /:/ \  \:\/:/__\/ \  \:\/:/__\/ \  \:\~~\__\/ \  \:\/:/__\/  \  \:\  /:/  \  \:\ /  /:/ \  \:\ /  /:/ \  \:\ /  /:/
  \  \:\  /:/   \  \:\        \  \:\  /:/   \  \::/       \  \::/       \  \:\        \  \::/        \  \:\/:/    \  \:\  /:/   \  \:\  /:/   \  \:\  /:/
   \  \:\/:/     \  \:\        \  \:\/:/     \  \:\        \  \:\        \  \:\        \  \:\         \  \::/      \  \:\/:/     \  \:\/:/     \  \:\/:/
    \  \::/       \  \:\        \  \::/       \  \:\        \  \:\        \  \:\        \  \:\         \__\/        \  \::/       \  \::/       \  \::/
     \__\/         \__\/         \__\/         \__\/         \__\/         \__\/         \__\/                       \__\/         \__\/         \__\/

*/

#include <bits/stdc++.h>
#include "grader.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll >
#define F first
#define S second
#define ld long double

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD=1e9+7;
const int  N=3e5+7;

long long po(ll x,ll y)
{
    ll ans=1;
    while(y){
        if(y & 1) ans=(ans*x);//%MOD;
        y/=2;
        x=(x*x);//%MOD;
    }
    return ans;
}

vector<ll>v[N];
vector<ll>eul;

void dfs(ll x,ll p)
{
    eul.pb(x);
    for(ll i=0;i<v[x].size();i++){
        if(v[x][i]!=p){
            dfs(v[x][i],x);
            eul.pb(x);
        }
    }
}


int findEgg(int n, vector < pair < int, int > > edj)
{
    for(ll i=0;i<edj.size();i++){
        v[edj[i].F].pb(edj[i].S);
        v[edj[i].S].pb(edj[i].F);
    }
    dfs(1,1);
    set<int>s;
    vector<int>que;
    ll l=0,r=eul.size()-1,mid;
    while(l<r){
        mid=(l+r)/2;
        for(ll i=0;i<=mid;i++) s.insert(eul[i]);
        for(set<int>::iterator it=s.begin();it!=s.end();it++){
            que.pb(*it);
        }
        if(query(que)) r=mid;
        else l=mid+1;
        s.clear();
        que.clear();
    }
    for(ll i=1;i<=n;i++) v[i].clear();
    eul.clear();
    return eul[l];
}

void solve()
{
    vector<pair<int,int> >edj;
    edj.pb({1,2});
    edj.pb({1,3});
    edj.pb({2,4});
    edj.pb({2,5});
    edj.pb({4,8});
    edj.pb({4,9});
    edj.pb({4,10});
    edj.pb({3,6});
    edj.pb({3,7});
    cout<<findEgg(10,edj);
}

/*
int main()
{
   // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);freopen("timeline.out","w",stdout);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
*/

Compilation message

eastereggs.cpp: In function 'void dfs(long long int, long long int)':
eastereggs.cpp:53:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(ll i=0;i<v[x].size();i++){
      |                ~^~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:64:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(ll i=0;i<edj.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
32.0 / 40.0

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

Subtask #2
34.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7368 KB Number of queries: 9
2 Partially correct 27 ms 7396 KB Number of queries: 10
3 Partially correct 38 ms 7412 KB Number of queries: 10
4 Partially correct 45 ms 7368 KB Number of queries: 10

Subtask #3
15.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 39 ms 7428 KB Number of queries: 10
2 Partially correct 31 ms 7404 KB Number of queries: 10
3 Partially correct 35 ms 7400 KB Number of queries: 10
4 Partially correct 37 ms 7416 KB Number of queries: 10