oj.uz

Submission #757245

# Submission time Handle Problem Language Result Execution time Memory
757245 2023-06-12T20:50:00 Z spicymango Burza (COCI16_burza) C++17
0 / 160
 204 ms 8808 KB 
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <deque>
#include <unordered_set>
#include <cctype>
#include <unordered_map>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <set>
#include <map>
#include <limits.h>
#include <cctype>
#include <cmath>
#include <bit>
#include <queue>
#include <numeric>
#include <iomanip>
using namespace std;
using ll = long long;
using ul = unsigned long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using qi = queue<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using di = deque<int>;
using dpi = deque<pii>;
using vpi = vector<pii>;
using tii = tuple<int, int, int>;
using vti = vector<tii>;
using qpi = queue<pii>;
using qti = queue<tii>;
using si = unordered_set<int>;
using sll = unordered_set<ll>;
using osll = set<ll>;
using osi = set<int>;
using osp = set<pii>;
using mosi = multiset<int>;
using mosc = multiset<char>;
using mpi = map<pii, int>;
using mip = map<int, pii>;
using miv = unordered_map<int, vi>;
using mii = unordered_map<int, int>;
using mill = unordered_map<int, ll>;
#define lso(S) ((S) & -(S))
const int MOD = 1e9 + 7;
const int F = 1e5;
const ll INF = 1e18;

vvi AL{};
vvi atdepth{};
int nleaves = 0;
pii intervals[400]{};
int dp[(1 << 20)]{};
int n, k;

void dfs(int u, int d, int p){
    if (d == k) {
        intervals[u] = {nleaves, nleaves + 1};
        ++nleaves;
        atdepth[k].push_back(u);
        return;
    }
    atdepth[d].push_back(u);
    intervals[u].first = 500;
    intervals[u].second = 0;
    for (int v: AL[u]){
        if (v == p) continue;
        dfs(v, d + 1, u);
        intervals[u].first = min(intervals[u].first, intervals[v].first);
        intervals[u].second = max(intervals[u].second, intervals[v].second);
    }
}
void solve(){
    scanf("%d %d", &n, &k);
    AL.assign(n, vi());
    atdepth.assign(k + 1, vi());
    for (int i = 0; i < n - 1; ++i){
        int u, v; scanf("%d %d", &u, &v); --u; --v;
        AL[u].push_back(v);
        AL[v].push_back(u);
    }
    dfs(0, 0, -1);
    // for (int i = 0; i < n; ++i){
    //     printf("%d %d %d\n", i, intervals[i].first, intervals[i].second);
    // }
    for (ll s = 1; s < (1 << k); ++s){
        for (int j = 1; j <= k; ++j){
            if (!(s & 1 << j)) continue;
            int prev_int = dp[s ^ j];
            for (int node : atdepth[j]){
                if (intervals[node].first <= prev_int) {
                    dp[s] = max(dp[s], intervals[node].second);
                }
            }
        }
    }
    if (dp[(1 << k) - 1] == nleaves) printf("DA\n");
    else printf("NE\n");
}
 
/*
    Did you read all of the input?
    Did you reset your data structures?
    Are your early exits correct?
    Is overflow possible?
    What happens for small n?
    Are you zero/one indexing correctly?
*/
int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    solve(); return 0;
    int tc; scanf("%d", &tc);
    while (tc--){
        solve();
    }
} 

// g++ -o tmp tmp.cpp -fsanitize=undefined -std=c++20

Compilation message

burza.cpp: In function 'void solve()':
burza.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
burza.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         int u, v; scanf("%d %d", &u, &v); --u; --v;
      |                   ~~~~~^~~~~~~~~~~~~~~~~
burza.cpp: In function 'int main()':
burza.cpp:120:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     int tc; scanf("%d", &tc);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 45 ms 832 KB Output is correct
3 Runtime error 177 ms 8676 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 720 KB Output is correct
2 Correct 55 ms 736 KB Output is correct
3 Runtime error 181 ms 8652 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 800 KB Output is correct
2 Correct 49 ms 724 KB Output is correct
3 Runtime error 200 ms 8808 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 432 KB Output is correct
2 Correct 49 ms 828 KB Output is correct
3 Runtime error 204 ms 8708 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 852 KB Output is correct
2 Correct 59 ms 852 KB Output is correct
3 Runtime error 180 ms 8764 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 820 KB Output is correct
2 Correct 43 ms 756 KB Output is correct
3 Runtime error 166 ms 8680 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 892 KB Output is correct
2 Correct 56 ms 764 KB Output is correct
3 Runtime error 168 ms 8704 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 444 KB Output is correct
2 Correct 49 ms 744 KB Output is correct
3 Runtime error 165 ms 8656 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 48 ms 764 KB Output is correct
3 Runtime error 194 ms 8680 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 468 KB Output is correct
2 Correct 46 ms 788 KB Output is correct
3 Runtime error 158 ms 8760 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -