Submission #920512

#	Time	Username	Problem	Language	Result	Execution time	Memory
920512		DON_F	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	257 ms	832 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
using ll = long long;
#define F first
#define S second

vector < vector < int > > g;
set < int > cur;
vector < int > vis;

int dfs(int j){
   vis[j] = 1;
   ll res = 1;
   for (auto &i : g[j]){
      if (!vis[i] && cur.count(i)){
        res += dfs(i);
      }
   }
   return res;
}
vector < int > go(int j){
   vector < int > tmp;
   tmp.push_back(j);
   vis[j] = 1;
   for (auto &i : g[j]){
     if (!vis[i] && cur.count(i)){
        vector < int > h = go(i);
        for (auto &k : h){
            tmp.push_back(k);
        }
     }
   }
   return tmp;
}

int findEgg (int n, vector < pair < int, int > > z){
    for (int i = 1; i <= n; ++i){
        cur.insert(i);
    }
    g = vector < vector < int > > (n + 1);
    for (int i = 0; i < n - 1; ++i){
        g[z[i].F].push_back(z[i].S);
        g[z[i].S].push_back(z[i].F);
    }
    while (cur.size() != 1){
        map < int, int > mp;
        for (auto &i : cur){
            vis = vector < int > (n + 1);
            mp[i] = dfs(i);
        }
        ll res = *cur.begin();
        for (auto &i : cur){
            if (abs(mp[res] - (int) cur.size() / 2) > abs(mp[i] - (int) cur.size() / 2))
                res = i;
        }
        vis = vector < int > (n + 1);
        vector < int > son = go(res);
        if (query(son)){
            cur.clear();
            for (int i = 0; i < son.size(); ++i){
                cur.insert(son[i]);
            }
        }else{
            for (int i = 0; i < son.size(); ++i){
                cur.erase(son[i]);
            }
        }
    }
    return *cur.begin();
}

Compilation message (stderr)

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for (int i = 0; i < son.size(); ++i){
      |                             ~~^~~~~~~~~~~~
eastereggs.cpp:66:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for (int i = 0; i < son.size(); ++i){
      |                             ~~^~~~~~~~~~~~

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