oj.uz

Submission #1097416

# Submission time Handle Problem Language Result Execution time Memory
1097416 2024-10-07T08:40:15 Z tinnhiemnn Burza (COCI16_burza) C++17
160 / 160
 31 ms 988 KB 
#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
const int N=405;
int n,k,dp[1<<20],l[N],r[N],Time;
vector<int> E[N],depth[22];

void dfs(int u, int pa, int d)
{
    depth[d].pb(u);

    if (d==k)
    {
        Time++;
        l[u]=Time; r[u]=Time;
        return;
    }

    l[u]=INT_MAX; r[u]=0;
    for (int v : E[u]) if (v!=pa)
    {
        dfs(v, u, d+1);
        l[u]=min(l[u], l[v]); r[u]=max(r[u], r[v]);
    }
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>k;
    if (k*k > n) {cout<<"DA"; return 0;}

    for (int i=1;i<n;i++)
    {
        int u,v; cin>>u>>v; E[u].pb(v); E[v].pb(u);
    }

    dfs(1, 0, 0);
    dp[0]=0;
    for (int mask=1; mask < (1<<k); mask++)
    {
        for (int i=0;i<k;i++) if ((mask>>i) & 1)
        {
            int cur = mask ^ (1<<i);
            for (int u : depth[i+1])
                if (l[u] <= dp[cur]+1) dp[mask]=max(dp[mask], r[u]);
        }
        if (dp[mask] == Time) {cout<<"DA"; return 0;}
    }
    cout<<"NE";

}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 28 ms 860 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 #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 856 KB Output is correct
2 Correct 27 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 28 ms 856 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 860 KB Output is correct
2 Correct 28 ms 856 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 #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 856 KB Output is correct
2 Correct 28 ms 860 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 472 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 952 KB Output is correct
2 Correct 27 ms 972 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 864 KB Output is correct
2 Correct 27 ms 860 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 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 28 ms 856 KB Output is correct
2 Correct 26 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 31 ms 856 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 29 ms 988 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 0 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 29 ms 856 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 612 KB Output is correct
6 Correct 1 ms 472 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 728 KB Output is correct
2 Correct 29 ms 752 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct