Submission #1099666

#TimeUsernameProblemLanguageResultExecution timeMemory
1099666tuannmEaster Eggs (info1cup17_eastereggs)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #include "grader.h" #define ii pair<int, int> #define fi first #define se second #define pb push_back using namespace std; const int maxN = 520; bool removed[maxN]; int sz[maxN], in[maxN], out[maxN], cnt; vector<int> adj[maxN]; bool isEgg[maxN]; bool query(vector<int> gg){ for(int i : gg) if(isEgg[i]) return true; return false; } void DFS(int u = 1, int p = 0){ in[u] = ++cnt; sz[u] = 1; for(int v : adj[u]){ if(removed[v] || v == p) continue; DFS(v, u); sz[u] += sz[v]; } out[u] = cnt; } int findEgg(int N, vector<ii> bridges){ for(auto [u, v] : bridges) adj[u].pb(v), adj[v].pb(u); for(int Q = 1; Q <= 60; ++Q){ cnt = 0; int root = 0; for(int i = 1; i <= N; ++i){ if(removed[i]) continue; root = i; break; } DFS(root); int zz = sz[root] / 2; int s = root; for(int i = 1; i <= N; ++i){ if(removed[i]) continue; if(abs(zz - sz[i]) < abs(zz - sz[s])) s = i; } vector<int> vec; for(int i = 1; i <= N; ++i){ if(removed[i]) continue; if(in[s] <= in[i] && in[i] <= out[s]) vec.pb(i); } if(query(vec)){ for(int i = 1; i <= N; ++i){ if(removed[i]) continue; if(in[s] <= in[i] && in[i] <= out[s]) continue; removed[i] = true; } } else{ for(int i : vec) removed[i] = true; } int cntRem = 0; for(int i = 1; i <= N; ++i) cntRem += !removed[i]; if(cntRem == 1){ for(int i = 1; i <= N; ++i) if(!removed[i]) return i; } } return -1; } /* mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r){ return l + rd() % (r - l + 1); } int main(){ for(int __ = 1; __ <= 100; ++__){ int N = Rand(512, 512); vector<ii> bridges; for(int i = 2; i <= N; ++i) bridges.pb({i, Rand(1, i - 1)}); for(int i = 1; i <= N; ++i) isEgg[i] = Rand(0, 1); int gg = Rand(1, N); isEgg[gg] = true; int u = findEgg(N, bridges); for(int i = 1; i <= N; ++i) removed[i] = false, adj[i].clear(); if(!isEgg[u]){ cout << "Wrong on test " << __ << ":\n"; cout << N << "\n"; for(auto [x, y] : bridges) cout << x << " " << y << "\n"; for(int i = 1; i <= N; ++i) if(isEgg[i]) cout << i << " "; cout << "\nYour answer: " << u << ".\n"; return 0; } for(int i = 1; i <= N; ++i) isEgg[i] = false; } cout << "OK.\n"; } */

Compilation message (stderr)

eastereggs.cpp:16:6: error: ambiguating new declaration of 'bool query(std::vector<int>)'
   16 | bool query(vector<int> gg){
      |      ^~~~~
In file included from eastereggs.cpp:2:
grader.h:6:5: note: old declaration 'int query(std::vector<int>)'
    6 | int query(vector < int > islands);
      |     ^~~~~