Submission #1181380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181380		Persia	Burza (COCI16_burza)	C++20	0 / 160	12 ms	1096 KiB

burza

#include <bits/stdc++.h>

using namespace std;

#define bit(i, x) (x >> i & 1)
#define ll long long
#define sz(x) (int)x.size()

const int N = 2e5 + 5;
const int mod = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
        return uniform_int_distribution<ll>(l, r)(rng);
}
template<typename T> void minimize(T &x, T y) {
        x = min(x, y);
}


int n, k;
vector<vector<int>> G;
vector<int> h;
vector<int> in;
vector<int> parr;
int cnt;
vector<vector<int>> lca;
vector<vector<int>> dp;

void dfs(int u, int par) {
        in[u] = ++cnt;
        parr[u] = par;
        for(int v : G[u]) if(v != par) {
                h[v] = h[u] + 1;
                dfs(v, u);
        }
}

void prepare() {
        dfs(1, -1);
        auto calc = [&](int x, int y) -> int {
                while(x != y) {
                        if(h[x] < h[y]) swap(x, y);
                        x = parr[x];
                }
                return x;
        };
        for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                        lca[i][j] = calc(i, j);
                }
        }
}

signed main(int argc, char* argv[]) {
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
    
        cin >> n >> k;
        G.assign(n + 1, vector<int>(0));
        h.assign(n + 1, 0);
        in.assign(n + 1, 0);
        parr.assign(n + 1, 0);
        lca.assign(n + 1, vector<int>(n + 1, 0));
        for(int i = 1; i < n; i++) {
                int x, y; cin >> x >> y;
                G[x].push_back(y);
                G[y].push_back(x);
        }
        prepare();
        
        // for(int i = 1; i <= n; i++) {
        //         for(int j = 1; j <= n; j++) {
        //                 cout << i << " " << j << " " << lca[i][j] << "\n";
        //         }
        // }
        // for(int i = 1; i <= n; i++) {
        //         cout << in[i] << " ";
        // }

        vector<int> v;
        v.push_back(0);
        for(int i = 1; i <= n; i++) {
                if(h[i] == k) {
                        v.push_back(i);
                }
        }
        int m = sz(v) - 1;
        if(m == 0) {
                cout << "DA";
                return 0;
        }
        dp.assign(m + 1, vector<int>(m + 1, 1e9));
        dp[0][0] = 0;
        for(int i = 1; i <= m; i++) {
                for(int j = 1; j <= i; j++) {
                        for(int l = 0; l < i; l++) {
                                int p = lca[v[l + 1]][v[i]];
                                if(h[p] >= j) {
                                        minimize(dp[i][j], dp[l][j - 1] + 1);
                                }                              
                        }
                }
        }
        int res = 1e9;
        for(int i = 1; i <= m; i++) {
                minimize(res, dp[m][i]);
        }
        if(res <= k) cout << "DA";
        else cout << "NE";

        return 0 ^ 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16