oj.uz

Submission #269732

# Submission time Handle Problem Language Result Execution time Memory
269732 2020-08-17T09:24:32 Z egekabas Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 3 ms 768 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
/*int query(vector < int > islands){
    return 1;
}*/
vector<int> g[600];
int ok[600];
int sz[600];
void calcsz(int v, int prt){
    sz[v] = 1;
    for(auto u : g[v]){
        if(u == prt || ok[u] == 0) continue;
        calcsz(u, v);
        sz[v] += sz[u];
    }
}
vector<int> curv, othv;
void get(int v, int prt, vector<int> &curv){
    curv.pb(v);
    for(auto u : g[v]){
        if(u == prt || ok[u] == 0) continue;
        get(u, v, curv);
    }
}
int dfs(int v, int prt){
    vector<pii> child;
    child.pb({-1, -1});
    for(auto u : g[v])
        if(ok[u])
            child.pb({sz[u], u});
    vector<bitset<20>> bs(child.size());
    bs[0][0] = 1;
    for(int i = 1; i < child.size(); ++i)
        bs[i] = (bs[i-1]|(bs[i-1]<<child[i].ff));
    int cur = (sz[v])/2;
    if(bs[child.size()-1][cur] == 0){
        for(auto u : g[v]){
            if(u == prt || ok[u] == 0) continue;
            int bef = sz[u];
            sz[u] = sz[v];
            sz[v] -= bef;
            if(dfs(u, v))
                return 1;
            sz[v] += bef;
            sz[u] = bef;
        }
        return 0;
    }
    curv.clear(); othv.clear();
    curv.pb(v);
    othv.pb(v);
    for(int i = child.size()-1; i >= 1; --i){
        if(cur-child[i].ff >= 0 && bs[i-1][cur-child[i].ff]){
            get(child[i].ss, v, curv);
            cur -= child[i].ff;
        }
        else
            get(child[i].ss, v, othv);
    }
    if(query(curv) == 0)
        swap(curv, othv);
    return 1;
}

int findEgg(int N, vector<pair<int, int>> bridges){
    for(auto u : bridges){
        g[u.ff].pb(u.ss);
        g[u.ss].pb(u.ff);
    }
    for(int i = 1; i <= N; ++i)
        curv.pb(i);
    while(1){
        if(curv.size() == 1) return curv[0];
        if(curv.size() == 2){
            if(query({curv[0]}))
                return curv[0];
            return curv[1];
        }
        for(int i = 1; i <= N; ++i)
            ok[i] = 0;
        for(auto u : curv)
            ok[u] = 1;
        int root = curv[0];
        calcsz(root, 0);
        dfs(root, 0);
    }
}
/*int main(){
    srand(time(NULL));
    cout << findEgg(10, {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {1, 10}}) << '\n';
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
}*/

Compilation message

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

Subtask #1
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -