oj.uz

Submission #735313

# Submission time Handle Problem Language Result Execution time Memory
735313 2023-05-04T01:21:22 Z Nhoksocqt1 Burza (COCI16_burza) C++17
160 / 160
 59 ms 1000 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 404;

vector<int> adj[MAXN], B[MAXN];
ii leafs[MAXN];
int dp[1 << 20];
int depth[MAXN], pa[MAXN], numNode, numTurn;

int dfs(int u, int p) {
    if(depth[u] == numTurn) {
        leafs[u].fi = leafs[u].se = ++leafs[0].fi;
        B[depth[u]].push_back(u);
        return depth[u];
    }

    leafs[u].fi = 1e9, leafs[u].se = 0;
    int maxDepth(depth[u]);
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(v != p) {
            pa[v] = u;
            depth[v] = 1 + depth[u];
            maxDepth = max(maxDepth, dfs(v, u));
            leafs[u].fi = min(leafs[u].fi, leafs[v].fi);
            leafs[u].se = max(leafs[u].se, leafs[v].se);
        }
    }

    if(maxDepth == numTurn)
        B[depth[u]].push_back(u);

    return maxDepth;
}

void process() {
    cin >> numNode >> numTurn;
    for (int i = 1; i < numNode; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if(numTurn * numTurn > numNode) {
        cout << "DA\n";
        return;
    }

    dfs(1, -1);
    for (int mask = 0; mask < (1 << numTurn); ++mask) {
        for (int i1 = ((1 << numTurn) - 1) ^ mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1);
            for (int it = 0; it < sz(B[i + 1]); ++it) {
                int u(B[i + 1][it]);
                if(leafs[u].fi <= dp[mask] + 1) {
                    dp[mask | (1 << i)] = max(dp[mask | (1 << i)], leafs[u].se);
                }
            }
        }
    }

    if(dp[(1 << numTurn) - 1] == leafs[1].se) {
        cout << "DA\n";
    } else {
        cout << "NE\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 59 ms 808 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 984 KB Output is correct
2 Correct 50 ms 852 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 51 ms 848 KB Output is correct
6 Correct 1 ms 352 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1000 KB Output is correct
2 Correct 50 ms 840 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 468 KB Output is correct
2 Correct 51 ms 880 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 356 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 872 KB Output is correct
2 Correct 49 ms 876 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 976 KB Output is correct
2 Correct 47 ms 808 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 880 KB Output is correct
2 Correct 49 ms 864 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 56 ms 980 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 504 KB Output is correct
2 Correct 49 ms 844 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 51 ms 880 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 608 KB Output is correct
2 Correct 47 ms 876 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 23 ms 596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct