Submission #1152168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152168		mmdrzada	Burza (COCI16_burza)	C++17	160 / 160	56 ms	35340 KiB

burza

#include <bits/stdc++.h>

using namespace std;
 
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
 
 
#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) int(x.size())
#define SP(x) setprecision(x) 
#define mod(x) (1ll*x%M+M)%M
#define p_q priority_queue
#define REP(i, k) for (int i = 0 ; i < k ; i ++)
#define mid (l+r)/2
const int K = 20, N = 401;
int n, k;
int dp[N][1<<K];
vi adj[N];
int h[N];
int timer;
int st[N], fn[N];
vector<pii> V;
int Low[N];

void dfs(int v = 0 , int p = -1) {
    h[v] = (p == -1 ? 0 : h[p] + 1);
    if (h[v] > k) return;
    if (p != -1) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), p));
    }
    st[v] = timer;
    if (h[v] == k) {
        timer++;
    }
    Low[v] = h[v];

    for(int neigh: adj[v]) {
        dfs(neigh, v);
        Low[v] = max(Low[v], Low[neigh]);
    }

    fn[v] = timer;
    if (Low[v] == k) {
    	h[v]--;
        V.pb({fn[v], v});
    }
}

void solve() {
    cin >> n >> k;
    if (k*k >= n) {
        cout << "DA\n";
        return;
    }
    for(int i = 0 ; i < n-1 ; i ++) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].pb(v), adj[v].pb(u);
    }

    dfs();

    sort(V.begin(), V.end());
    memset(dp[0], true, sizeof dp[0]);
    for(auto [f, v]: V) {
        for(int mask = 0 ; mask < 1<<k ; mask ++) {
            if (mask>>h[v]&1) {
                dp[f][mask] |= dp[st[v]][mask^(1<<h[v])];
            }
        }
    }
    
    cout << (dp[timer][(1<<k)-1] ? "DA" : "NE") << endl;
}

int32_t main() {
	fastIO;

	solve();

    return 0;
}

• 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