oj.uz

Submission #727461

# Submission time Handle Problem Language Result Execution time Memory
727461 2023-04-20T19:54:21 Z YugiHacker Burza (COCI16_burza) C++17
160 / 160
 53 ms 3308 KB 
/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 402
#define bit(mask,i) ((mask>>i)&1)
using namespace std;
int n, k, d[maxn], cnt, in[maxn], out[maxn];
bool f[maxn][1 << 20];
vector <int> h[maxn];
vector <int> a[maxn];
void dfs(int u, int p = -1)
{
    if (d[u] == k)
    {
        in[u] = cnt;
        out[u] = ++cnt;
        return;
    }
    in[u] = cnt;
    for (int v:a[u]) if (v!=p)
    {
        d[v] = d[u] + 1;
        dfs(v, u);
    }
    out[u] = cnt;
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    if (k * k >= n) return cout << "DA", 0;
    f1 (i, n-1)
    {
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    memset(d, -1, sizeof d);
    d[1] = 0;
    dfs(1);
    for (int i=2; i<=n; i++) if(out[i]) h[in[i]].push_back(i);
    f[0][0] = 1;
    for (int i=0; i<cnt; ++i)
    {
        f0 (mask, 1 << k)
        {
            if (f[i][mask])
            {
                for (int u:h[i])
                    if (!bit(mask, d[u] - 1))
                        f[out[u]][mask ^ (1 << d[u] - 1)] = 1;
            }
        }
    }
    f0 (mask, 1 << k) if (f[cnt][mask]) return cout << "DA", 0;
    cout << "NE";
}

Compilation message

burza.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main()
      | ^~~~
burza.cpp: In function 'int main()':
burza.cpp:55:41: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   55 |                     if (!bit(mask, d[u] - 1))
      |                                    ~~~~~^~~
burza.cpp:10:29: note: in definition of macro 'bit'
   10 | #define bit(mask,i) ((mask>>i)&1)
      |                             ^
burza.cpp:56:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |                         f[out[u]][mask ^ (1 << d[u] - 1)] = 1;
      |                                                ~~~~~^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 32 ms 2528 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2776 KB Output is correct
2 Correct 32 ms 2460 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 50 ms 2968 KB Output is correct
6 Correct 1 ms 980 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2764 KB Output is correct
2 Correct 34 ms 2508 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 856 KB Output is correct
6 Correct 1 ms 476 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1316 KB Output is correct
2 Correct 47 ms 3308 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 476 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2232 KB Output is correct
2 Correct 40 ms 2852 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 988 KB Output is correct
6 Correct 1 ms 864 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2636 KB Output is correct
2 Correct 39 ms 2768 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 768 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2840 KB Output is correct
2 Correct 44 ms 2692 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 52 ms 3168 KB Output is correct
6 Correct 1 ms 852 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1172 KB Output is correct
2 Correct 41 ms 2636 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 980 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 53 ms 2964 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 988 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1624 KB Output is correct
2 Correct 50 ms 2964 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 21 ms 1612 KB Output is correct
6 Correct 1 ms 596 KB Output is correct