oj.uz

Submission #484266

# Submission time Handle Problem Language Result Execution time Memory
484266 2021-11-02T18:21:08 Z Tenis0206 Easter Eggs (info1cup17_eastereggs) C++11
100 / 100
 14 ms 2760 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

int cnt = 0;

int n;

vector<int> G[100005];

int p[100005],fr[100005];
int l[100005],s[100005];

/*int ou = 0;

bool query(vector<int> v)
{
    for(auto it : v)
    {
        if(it==ou)
        {
            return true;
        }
    }
    return false;
}
*/

void dfs(int nod, int dad = 0)
{
    p[++cnt] = nod;
    l[nod] = cnt;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        dfs(it,nod);
        p[++cnt] = nod;
    }
}

vector<int> get_query(int st, int dr)
{
    vector<int> rez;
    for(int i=st;i<=dr;i++)
    {
        if(!fr[p[i]])
        {
            rez.push_back(p[i]);
        }
        ++fr[p[i]];
    }
    for(int i=st;i<=dr;i++)
    {
        fr[p[i]] = 0;
    }
    return rez;
}

bool cmp(int a, int b)
{
    return l[a] < l[b];
}

int findEgg(int N, vector<pair<int,int>> e)
{
    n = N;
    for(auto it : e)
    {
        int x = it.first;
        int y = it.second;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        s[i] = i;
    }
    sort(s+1,s+n+1,cmp);
    int st = 1;
    int dr = n;
    while(st<dr)
    {
        int mij = (st+dr)>>1;
        vector<int> q = get_query(l[s[st]],l[s[mij+1]]-1);
        if(query(q))
        {
            dr = mij;
        }
        else
        {
            st = mij+1;
        }
    }
    cnt = 0;
    for(int i=1;i<=n;i++)
    {
        G[i].clear();
    }
    return s[st];
}

/*int main()
{
    int n;
    cin>>n>>ou;
    vector<pair<int,int>> e;
    for(int i=1;i<n;i++)
    {
         int x,y;
         cin>>x>>y;
         e.push_back({x,y});
    }
    cout<<findEgg(n,e);
    return 0;
}
*/

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2632 KB Number of queries: 8
2 Correct 9 ms 2632 KB Number of queries: 9
3 Correct 10 ms 2632 KB Number of queries: 9
4 Correct 12 ms 2632 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2632 KB Number of queries: 9
2 Correct 7 ms 2632 KB Number of queries: 9
3 Correct 14 ms 2760 KB Number of queries: 9
4 Correct 11 ms 2632 KB Number of queries: 9