oj.uz

Submission #872054

# Submission time Handle Problem Language Result Execution time Memory
872054 2023-11-12T08:01:08 Z MON Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 12 ms 476 KB 
#include<iostream>
#include<vector>
using namespace std;

int query(vector<int> islands);

vector<int> vecini[513]; vector<int> v = {0};

void dfs(int a,int p = -1)
{
    v.emplace_back(a);
    for(auto &it : vecini[a])
        if(it != p) dfs(it,a);
}

vector<int> get(int p)
{
    vector<int> g;
    for(int i = 1; i <= p ; i++) g.emplace_back(v[i]);
    return g;
}

int findEgg(int N, vector<pair<int,int>> bridges)
{
    for(int i = 1; i <= 512; i++) vecini[i].clear(); v.clear(); v.emplace_back(0);
    for(auto &it : bridges) vecini[it.first].emplace_back(it.second),vecini[it.second].emplace_back(it.first);
    dfs(1); int n = N;
    int pas = 1, ans = 0; while(pas <= n) pas <<= 1;
    for(; pas ; pas >>= 1)
        if(ans + pas < n) ans += pas * (1 ^ query(get(ans+pas)));
    return v[ans + 1];
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:25:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   25 |     for(int i = 1; i <= 512; i++) vecini[i].clear(); v.clear(); v.emplace_back(0);
      |     ^~~
eastereggs.cpp:25:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   25 |     for(int i = 1; i <= 512; i++) vecini[i].clear(); v.clear(); v.emplace_back(0);
      |                                                      ^

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Number of queries: 8
2 Correct 7 ms 468 KB Number of queries: 9
3 Correct 12 ms 344 KB Number of queries: 9
4 Correct 10 ms 476 KB Number of queries: 9

Subtask #3
20.0 / 20.0

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