oj.uz

답안 #529689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529689 2022-02-23T12:46:58 Z ohohorz Easter Eggs (info1cup17_eastereggs) C++14
10 / 100
 2 ms 704 KB 
#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int MAXN = 520;
set<int> g[MAXN];
int n, sub[MAXN];
vector<int> cenTree[MAXN], what[MAXN];

int dfs(int u,int p){
    sub[u] = 1;
    for(auto v:g[u]) if(v != p){
        sub[u] += dfs(v, u);
    }
    return sub[u];

}
int centroid(int u, int p, int mx){
    for(auto v:g[u]) if(v != p){
        if(sub[v] > (mx / 2)) return centroid(v, u, mx);
    }
    return u;
}
void make(int u, int p){
    int mx = dfs(u, p);
    int c = centroid(u, p, mx);
    if(p == 0) p = c;
    else{
        cenTree[p].push_back(c);
        cenTree[c].push_back(p);
    }
    
    vector<int> temp(g[c].begin(), g[c].end());
    for(auto v:temp){
        g[c].erase(v);
        g[v].erase(c);
        make(v, c);
    }
}

void dfs2(int u,int p){
    what[u].push_back(u);
    for(auto v:cenTree[u]) if(v != p){
        dfs2(v, u);
        for(auto x:what[v]) what[u].push_back(x);
    }
}

int get(int u,int p){
    for(auto v:cenTree[u]) if(v != p){
        vector<int> lol;
        for(auto w:cenTree[v]){
            if(w == u) continue;
            for(auto k:what[w]) lol.push_back(k);
        }
        lol.push_back(v);
        // cout << v << " -> ";
        // for(auto k:lol) cout << k << " ";
        // cout << endl;
        int q = query(lol);
        if(q == 1){
            // cout << v << endl;
            return get(v, u);
        }
    }
    return u;
}


int findEgg (int N, vector < pair < int, int > > bridges){   
    /*
    set<int> g[MAXN];
int n, sub[MAXN];
vector<int> cenTree[MAXN], what[MAXN];
    */
   for(int i = 0;i <MAXN;i++){
       sub[i] = 0;
       cenTree[i].clear();
       what[i].clear();
       g[i].clear();
   }
    
    n = N;
    for(int i = 0;i < N-1;i++){
        int u = bridges[i].first;
        int v = bridges[i].second;
        g[u].insert(v);
        g[v].insert(u);
    }

    make(1, 0);
    dfs2(1, 0);
    
    return get(1, 0);
}

Subtask #1
10.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 328 KB Number of queries: 6
2 Partially correct 1 ms 328 KB Number of queries: 6
3 Partially correct 1 ms 328 KB Number of queries: 10
4 Partially correct 2 ms 328 KB Number of queries: 15

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 584 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -