oj.uz

Submission #968579

# Submission time Handle Problem Language Result Execution time Memory
968579 2024-04-23T16:10:54 Z Hadi_Alhamed Burza (COCI16_burza) C++17
160 / 160
 404 ms 15828 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define siz(x) (int)x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
//===========================================
const int MAX = 405;
vi adj[MAX];
int p[MAX], dep[MAX], depb[MAX];//depb : number of nodes below this node (subtree_size of Node without considering the root of this subtree
set<vi> vis;

void dfs(int v){
    for (int u: adj[v]){
        if (u == p[v]) continue;
        p[u] = v;
        dep[u] = dep[v]+1;
        dfs(u);
        depb[v] = max(depb[v], depb[u]+1);
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1);
    queue<vi> q; q.push({1});
    while (siz(q)){
        auto vec = q.front(); q.pop();
        if (vec.empty()){
            cout << "DA\n";
            return 0;
        }
        int rem = k-dep[vec[0]];//all elements of vec have same depth
        vi vv;//new level nodes that we need to consider
        for (int v: vec){
            for (int u: adj[v]){
                if (u == p[v]) continue;
                if (depb[u]+1 >= rem) vv.pb(u);//because if it has less size than the remaining then forsure going in this route will cause the game to end in less than K move
            }
        }
        if (siz(vv) > rem) continue;//there is no way for the game to end in less than K move
        for (int i = 0; i < siz(vv); i++){
            swap(vv[i], vv.back());
            vector<int> temp = vv; temp.pop_back(); sort(all(temp));//for each node from vv try deleting it , if we get new state then add it to the queue
            if (!vis.count(temp)){
                q.push(temp);
                vis.insert(temp);
            }
            swap(vv[i], vv.back());
        }
    }
    cout << "NE\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2128 KB Output is correct
2 Correct 404 ms 15508 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 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 15600 KB Output is correct
2 Correct 354 ms 15600 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 354 ms 15600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 15536 KB Output is correct
2 Correct 350 ms 15440 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 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3976 KB Output is correct
2 Correct 360 ms 15476 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 472 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 15440 KB Output is correct
2 Correct 357 ms 15668 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 15464 KB Output is correct
2 Correct 395 ms 15452 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 0 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 15464 KB Output is correct
2 Correct 344 ms 15464 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 355 ms 15592 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4180 KB Output is correct
2 Correct 352 ms 15540 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 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 #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2128 KB Output is correct
2 Correct 360 ms 15828 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 7844 KB Output is correct
2 Correct 348 ms 15468 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 150 ms 7900 KB Output is correct
6 Correct 1 ms 348 KB Output is correct