oj.uz

Submission #153524

# Submission time Handle Problem Language Result Execution time Memory
153524 2019-09-14T12:39:38 Z nicolaalexandra Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 21 ms 380 KB 
#include <iostream>
#include "grader.h"
#include <vector>
#include <algorithm>
#define DIM 1000
using namespace std;
vector <int> E,v,L[DIM];

/*int query (vector <int> v){
    for (int i=0;i<v.size();i++)
        cout<<v[i]<<" ";
    cout<<endl;
    int ans;
    cin>>ans;
    return ans;
}*/

void dfs (int nod, int tata){
    E.push_back(nod);
    for (int i=0;i<L[nod].size();i++){
        int vecin = L[nod][i];
        if (vecin != tata)
            dfs (vecin,nod);
    }
    //E.push_back(nod);
}
int verif (int poz1, int poz2){
    v.clear();
    for (int i=poz1;i<=poz2;i++)
        v.push_back(E[i]);
    //sort (v.begin(),v.end());
    //v.resize(unique(v.begin(),v.end())-v.begin());
    return query (v);
}
int findEgg (int n, vector <pair<int,int> > mch){
    for (int i=1;i<=n;i++)
        L[i].clear();
    for (int i=0;i<n-1;i++){
        int x = mch[i].first, y = mch[i].second;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    E.clear();
    dfs (1,0);
    int st = 0, dr = E.size()-1;
    while (st < dr){
        int mid = (st+dr)>>1;
        if (verif (0,mid))
            dr = mid;
        else st = mid+1;
    }
    return E[st];
}
/*int main (){

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        mch.push_back(make_pair(x,y));
    }
    cout<<findEgg (n,mch);


    return 0;
}*/

Compilation message

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<L[nod].size();i++){
                  ~^~~~~~~~~~~~~~

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 300 KB Number of queries: 4
2 Correct 4 ms 252 KB Number of queries: 4
3 Correct 3 ms 380 KB Number of queries: 4
4 Correct 2 ms 376 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Number of queries: 8
2 Correct 15 ms 376 KB Number of queries: 9
3 Correct 16 ms 364 KB Number of queries: 9
4 Correct 19 ms 248 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 376 KB Number of queries: 9
2 Correct 18 ms 376 KB Number of queries: 9
3 Correct 20 ms 248 KB Number of queries: 9
4 Correct 21 ms 376 KB Number of queries: 9