Submission #727461

#	Time	Username	Problem	Language	Result	Execution time	Memory
727461		YugiHacker	Burza (COCI16_burza)	C++17	160 / 160	53 ms	3308 KiB

burza

/*
	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 (stderr)

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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16