oj.uz

Submission #763497

# Submission time Handle Problem Language Result Execution time Memory
763497 2023-06-22T11:31:12 Z Quan2003 Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 26 ms 23888 KB 
#include "grader.h"
#include "bits/stdc++.h"
using namespace std; 
#define MAXN (int) 1e6 + 5 
#define mp make_pair
#define pii pair<int,int>
vector<int> order; 
vector<int>adj[MAXN]; 
void dfs(int u, int p)
{
     order.push_back(u); 
     for(int i = 0; i < (int) adj[u].size(); i++)
     {
         int v = adj[u][i];
         if(v == p) continue; 
         dfs(v,u); 
     }
}
int findEgg(int n, vector<pii> bridges)
{
     for(int i = 1; i <= n; i++) adj[i].clear(); 
     order.clear(); 
     for(int i = 0; i < (int) bridges.size(); i++)
     {
         int u = bridges[i].first; 
         int v = bridges[i].second;
         adj[u].push_back(v);
         adj[v].push_back(u); 
     }
     dfs(1, 0); 
     int l = 0; 
     int r = n - 1; 
     while(l < r)
     {
         int mid = (l + r + 1) / 2;
         if(query(vector<int>(order.begin(), order.begin() + mid))) r = mid - 1; 
         else l = mid; 
     }
     return order[l]; 
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23760 KB Number of queries: 4
2 Correct 12 ms 23768 KB Number of queries: 4
3 Correct 12 ms 23716 KB Number of queries: 4
4 Correct 14 ms 23888 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23820 KB Number of queries: 8
2 Correct 22 ms 23832 KB Number of queries: 9
3 Correct 26 ms 23812 KB Number of queries: 9
4 Correct 22 ms 23760 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23840 KB Number of queries: 9
2 Correct 26 ms 23812 KB Number of queries: 9
3 Correct 23 ms 23840 KB Number of queries: 9
4 Correct 25 ms 23824 KB Number of queries: 9