oj.uz

Submission #920515

# Submission time Handle Problem Language Result Execution time Memory
920515 2024-02-02T16:52:00 Z DON_F Easter Eggs (info1cup17_eastereggs) C++14
26.4 / 100
 13 ms 784 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);
    }
    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: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.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Number of queries: 5
2 Partially correct 1 ms 344 KB Number of queries: 5
3 Partially correct 1 ms 344 KB Number of queries: 6
4 Partially correct 1 ms 344 KB Number of queries: 8

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 480 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 13 ms 784 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -