Submission #920515

#	Time	Username	Problem	Language	Result	Execution time	Memory
920515		DON_F	Easter Eggs (info1cup17_eastereggs)	C++14	26.40 / 100	13 ms	784 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);
    }
    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:61:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for (int i = 0; i < son.size(); ++i){
      |                             ~~^~~~~~~~~~~~
eastereggs.cpp:65:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int i = 0; i < son.size(); ++i){
      |                             ~~^~~~~~~~~~~~

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