oj.uz

답안 #975345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975345 2024-05-04T22:27:00 Z u_suck_o Burza (COCI16_burza) C++17
160 / 160
 32 ms 964 KB 
#include <iostream>
#include <vector>
#define l first
#define r second
#include <climits>
using namespace std;

vector<pair<int,int>> intv(405, make_pair(INT_MAX,INT_MIN));
int range[1 << 20];
vector<int> nodesAtDepth[21];
vector<int> adj[405];
int leaf;
int N, K;
bool dfs(int node, int parent, int dep) {
    if (dep == K) {
        ++leaf;
        nodesAtDepth[dep].push_back(node);
        intv[node] = {leaf,leaf};
        return true;
    }
    bool valid = false;
    for (auto child: adj[node]) {
        if (child != parent) {
            if ( dfs(child, node, dep+1) ) {
                if (intv[child].l < intv[node].l) intv[node].l = intv[child].l;
                if (intv[child].r > intv[node].r) intv[node].r = intv[child].r;
                valid = true;
            }
        }
    }
    if (!valid) return false;
    nodesAtDepth[dep].push_back(node);
    return true;
}

int main() {
  
    std::cin >> N >> K;
    
    for (int e = 1; e <= N - 1; e++) {
        int n1, n2;
        cin >> n1 >> n2;
        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
    }

    if (K * K >= N) {
        cout << "DA" << endl;
        return 0;
    }
    
    // find all leaf nodes
    dfs(1, -1, 0);

    range[0] = 0;
    for (int mask = 1; mask < (1 << K); mask++) {
        int curr = range[mask];
        // go through each possible previous masks
        for (int lastBit = 0; lastBit < K; lastBit++) {
            if ((mask & (1 << lastBit)) != 0) {
                int prev = range[mask & ~(1 << lastBit)];
                // find the best node at given depth
                for (int n : nodesAtDepth[lastBit + 1]) {
                    if (intv[n].first <= prev + 1) {
                        curr = std::max(curr, intv[n].second);
                        range[mask] = curr;
                    }
                }
            }
        }

        if (range[mask] == leaf) {
            cout << "DA" << endl;
            return 0;
        }
    }

    cout << "NE" << endl;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 29 ms 852 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 876 KB Output is correct
2 Correct 30 ms 956 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 29 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 860 KB Output is correct
2 Correct 28 ms 932 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 604 KB Output is correct
2 Correct 29 ms 848 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 860 KB Output is correct
2 Correct 28 ms 856 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 856 KB Output is correct
2 Correct 29 ms 896 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 860 KB Output is correct
2 Correct 28 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 27 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 29 ms 964 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 29 ms 924 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 456 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 604 KB Output is correct
2 Correct 29 ms 860 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 13 ms 524 KB Output is correct
6 Correct 1 ms 348 KB Output is correct