Submission #759716

#	Time	Username	Problem	Language	Result	Execution time	Memory
759716		jay_jayjay	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	3089 ms	336 KiB

eastereggs

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <deque>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f

#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#include <assert.h>
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#define assert(args...) 42
#endif
// 1}}}

int query(vector<int> islands);

int findEgg(int n, vector<pair<int,int>> edges) {
        for(auto&[a,b]:edges)a--,b--;

        vector<vector<int>> adj(n);
        for(auto [a,b]:edges) adj[a].push_back(b),adj[b].push_back(a);

        set<int> vs;
        for(int i=0;i<n;i++)vs.insert(i);

        auto dfs = [&](auto& self, int u, int p) -> int {
                if(!vs.count(u))return 0;
                int sz=1;
                for(auto x:adj[u])if(x!=p)sz+=self(self,x,u);
                return sz;
        };

        auto doquery = [&](int u, int p) {
                deque<int> dq;
                dq.push_back(u);
                vector<bool> vis(n);
                vector<int> q;
                while(dq.size()) {
                        int v=dq.front(); dq.pop_front();
                        if(vis[v])continue;
                        if(!vs.count(v))continue;
                        vis[v]=1;
                        q.push_back(1+v);

                        for(auto x:adj[v])if(x!=p)dq.push_back(x);
                }
                //for(auto j:q)printf("%d ",j);
                int x=query(q);
                //printf("%d\n",x);
                for(auto&j:q)j--;
                if(x) vs = set<int>{q.begin(),q.end()};
                else for(auto jj:q)vs.erase(jj);
        };

        while(vs.size()&~1) {
                //for(auto x:vs)printf("%d ",x);
                //printf("\t\t%d\n\n\n",vs.size());
                for (auto [u,v]: edges) {
                        //printf("try edge %d %d\n",u,v);
                        if(vs.count(u)&&vs.count(v)) {
                                // mayb?
                                int sz=dfs(dfs,u, v);
                                //printf("sz=%d\n",sz);
                                if(sz==vs.size()/2 || sz==vs.size()/2+1) {
                                        //printf("q!\n");
                                        doquery(u,v);
                                        goto nxt;
                                }
                        }
                }
                assert(0);
                nxt:;
        }
        return 1+*vs.begin();
}
#undef DEBUG
#ifdef DEBUG
int main()
{
}
#endif

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for(auto&[a,b]:edges)a--,b--;
      |                  ^
eastereggs.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto [a,b]:edges) adj[a].push_back(b),adj[b].push_back(a);
      |                  ^
eastereggs.cpp:73:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |                 for (auto [u,v]: edges) {
      |                           ^
eastereggs.cpp:79:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                                 if(sz==vs.size()/2 || sz==vs.size()/2+1) {
      |                                    ~~^~~~~~~~~~~~~
eastereggs.cpp:79:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                                 if(sz==vs.size()/2 || sz==vs.size()/2+1) {
      |                                                       ~~^~~~~~~~~~~~~~~
eastereggs.cpp:26:25: warning: statement has no effect [-Wunused-value]
   26 | #define assert(args...) 42
      |                         ^~
eastereggs.cpp:86:17: note: in expansion of macro 'assert'
   86 |                 assert(0);
      |                 ^~~~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20