oj.uz

답안 #389247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389247 2021-04-14T01:39:26 Z cheissmart Easter Eggs (info1cup17_eastereggs) C++14
10 / 100
 21 ms 584 KB 
#include <bits/stdc++.h>
#include "grader.h"
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << "): " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 520;

vi G[N];
int vis[N], sz[N], tot;

void init(int n) {
    for(int i = 1; i <= n; i++) {
        G[i].clear();
        vis[i] = 0;
    }
}

int dfs_sz(int u, int p = 0) {
    sz[u] = 1;
    for(int v:G[u]) if(v != p && !vis[v]) {
        sz[u] += dfs_sz(v, u);
    }
    return sz[u];
}

int get_c(int u, int p = 0) {
    int mx = 0;
    for(int v:G[u]) if(v != p && !vis[v]) {
        int cc = get_c(v, u);
        mx = max(mx, sz[v]);
        if(cc) return cc;
    }
    if(max(mx, tot - sz[u]) * 2 <= tot) return u;
    return 0;
}

vi s;

void dfs(int u, int p) {
    s.PB(u);
    for(int v:G[u]) if(v != p && !vis[v]) dfs(v, u);
}

int go(int u) {
    tot = dfs_sz(u);
    int c = get_c(u);
    vi ch;
    for(int v:G[c]) if(!vis[v]) {
        ch.PB(v);
    }
    if(ch.empty()) return c;
    dfs_sz(c);
    int v = ch[0];
    for(int tt:ch) {
        if(sz[tt] > sz[v])
            v = tt;
    }
    s.clear();
    dfs(v, c);
    if(query(s)) {
        vis[c] = 1;
        return go(v);
    }
    vis[v] = 1;
    return go(c);
}

int findEgg(int n, V<pi> es) {
    init(n);
    for(pi p:es) G[p.F].PB(p.S), G[p.S].PB(p.F);
    return go(1);
}

Subtask #1
10.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Number of queries: 4
2 Partially correct 1 ms 200 KB Number of queries: 5
3 Partially correct 2 ms 200 KB Number of queries: 9
4 Partially correct 4 ms 200 KB Number of queries: 15

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 328 KB Number of queries: 8
2 Partially correct 12 ms 328 KB Number of queries: 12
3 Partially correct 17 ms 328 KB Number of queries: 28
4 Runtime error 2 ms 584 KB Execution killed with signal 6

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 328 KB Number of queries: 9
2 Partially correct 13 ms 328 KB Number of queries: 12
3 Partially correct 21 ms 328 KB Number of queries: 28
4 Runtime error 2 ms 456 KB Execution killed with signal 6