oj.uz

Submission #920512

# Submission time Handle Problem Language Result Execution time Memory
920512 2024-02-02T16:41:27 Z DON_F Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 257 ms 832 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 436 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 504 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 832 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -