oj.uz

Submission #514694

# Submission time Handle Problem Language Result Execution time Memory
514694 2022-01-18T11:24:51 Z amukkalir Easter Eggs (info1cup17_eastereggs) C++17
10 / 100
 3 ms 512 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
#define pb push_back 

const int nax = 512; 
vector<int> adj[nax+5]; //adjecency list, sorted by numbers of subtree
int p[nax+5], h[nax+5]; //parent of i, depth of i
int sub[nax+5]; //number of vertices in subtree with root i 

vector<int> divide(vector<int> &v) {
    //wanna divide vector v of size n to res of size n/2
    //v should have been sorted
    int n = v.size(); 
    int m = n/2; 

    sort(v.begin(), v.end(), [](int a, int b) {
        return h[a] < h[b]; 
    }); //sort by highest position

    vector<int> res; 

    auto cmp = [](int a, int b) {return h[a] < h[b];}; 
    set<int, decltype(cmp)> tmp(cmp); 

    function <void(int)> rec = [&] (int u) {
        tmp.insert(u); 
        if(tmp.size() == m) return; 
        
        for(int v : adj[u]) rec(v); 
    }; 

    for(int i=0; i<n; i++) {
        if(tmp.count(v[i])) continue; 
        if(tmp.size() == m) break; 
        //try adding v[i]
        rec(v[i]); 
    }

    for(int i : tmp) res.pb(i); 

    return res; 
}

void dfs(int u, int prv, int d) {
    p[u] = prv; 
    sub[u] = 1, 
    h[u] = d; 

    int x = adj[u].size(); 
    for(int i = 0; i < x; i++) { 
        int v = adj[u][i]; 
        if(v == prv) {
            adj[u][i] = nax+2; 
        } else {
            dfs(v, u, d+1); 
            sub[u] += sub[v]; 
        }
    }

    sort(adj[u].begin(), adj[u].end(), [](int a, int b){
        return sub[a] < sub[b]; 
    }); 
    if(u!=1) adj[u].pop_back(); //pop back the parent (which have been changed into nax+1)
}

int get_lca(int a, int b) { //return the lca of a and b 
    //use sparse table 
    return 0; 
}

bool ask(vector<int> s) { //ask this set of vertices
    //make sure they are ALL connected 
    int lca = s[0]; 
    for(int i=1; i<s.size(); i++) lca = get_lca(lca, s[i]); 

    unordered_set<int> tmp; tmp.insert(lca); 
    //for each vertex, add their path up to lca 
    for(int i=0; i<s.size(); i++) {
        int a = s[i]; 
        while(a != lca) {
            tmp.insert(a); 
            //if any of theese doesn't actually belong in the original set
            //it should have been asked and eliminated from the set of possible answers
            a = p[a]; 
        }
    }

    s.clear(); //pindahin tmp ke s
    for(int i : tmp) s.push_back(i); 
    return query(s); 
}

int n; 

void cek() {
    for(int i=1; i<=n; i++) {
        cout << i << " " << h[i] << " " << sub[i] << " " << p[i] << endl; 
        cout << "adj " << i << " : "; 
        for(int v : adj[i]) cout << v << " "; 
        cout << endl << endl; 
    }
}

bool ok(int u) {
    vector<int> vec; 
    function<void(int)> get = [&] (int u) {
        vec.pb(u); 
        for(int v : adj[u]) get(v); 
    }; 

    get(u); 

    // cout << "asking "; 
    // for(int x : vec) cout << x << " "; 
    // cout << endl; 

    return query(vec); 
}

int findEgg (int N, vector < pair < int, int > > bridges)
{   
    
    vector<int> v; 
    sub[nax+2] = 2*N; 
    n = N; 

    for(int i=1; i<=N; i++) {
        v.pb(i); 
        adj[i].clear(); 
        h[i] = 0; 
        sub[i] = 0; 
        p[i] = 0; 
    }

    for(int i=0; i+1<N; i++) {
        int a = bridges[i].first; 
        int b = bridges[i].second; 
        adj[a].pb(b); 
        adj[b].pb(a); 
    }

    dfs(1,1,0); //make rooted tree

    //cek(); 

    int ans = 0; 
    function<void(int)> f = [&] (int u){
//puts("HERE"); 
        for(int v : adj[u]) {
            if(ok(v)) f(v); 
        }
        if(adj[u].size() == 0) ans = u; 

        if(ans) return; 
        ans = u; 
    }; 

    f(1); 
//puts("HERE"); 
//cout << ans << endl; 
    // while(v.size()!=1) {

    // }

    return ans;
}

Compilation message

eastereggs.cpp: In lambda function:
eastereggs.cpp:29:23: warning: comparison of integer expressions of different signedness: 'std::set<int, divide(std::vector<int>&)::<lambda(int, int)> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |         if(tmp.size() == m) return;
      |            ~~~~~~~~~~~^~~~
eastereggs.cpp: In function 'std::vector<int> divide(std::vector<int>&)':
eastereggs.cpp:36:23: warning: comparison of integer expressions of different signedness: 'std::set<int, divide(std::vector<int>&)::<lambda(int, int)> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         if(tmp.size() == m) break;
      |            ~~~~~~~~~~~^~~~
eastereggs.cpp: In function 'bool ask(std::vector<int>)':
eastereggs.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=1; i<s.size(); i++) lca = get_lca(lca, s[i]);
      |                  ~^~~~~~~~~
eastereggs.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0; i<s.size(); i++) {
      |                  ~^~~~~~~~~

Subtask #1
10.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 200 KB Number of queries: 9
2 Partially correct 1 ms 284 KB Number of queries: 10
3 Partially correct 1 ms 200 KB Number of queries: 13
4 Partially correct 2 ms 200 KB Number of queries: 15

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 476 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 3 ms 512 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -