oj.uz

Submission #659227

# Submission time Handle Problem Language Result Execution time Memory
659227 2022-11-17T05:29:15 Z playnvc Burza (COCI16_burza) C++14
160 / 160
 58 ms 3204 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=a; i<b; i++)

typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAX = 405, MAXK = 20;

int n, k;
vector <int> V[MAX];
vector <int> Q[MAX];
int disc_list[MAX], fin_list[MAX];
int dub[MAX];
int vr;
char dp[MAX][1<<MAXK];

void dfs(int node, int prosli)
{
  if (node)
    dub[node] = dub[prosli] + 1;

  if (dub[node] == k - 1) {
    disc_list[node] = vr++;
    fin_list[node] = vr;
    return;
  }

  disc_list[node] = vr;

  for (auto it : V[node])
    if (it != prosli)
      dfs(it, node);

  fin_list[node] = vr;
}

int rijesi()
{
  dp[0][0] = 1;

  FOR(i, 1, n)
    Q[disc_list[i]].push_back(i);

  REP(i, vr) {
    REP(j, (1<<k)) {
      if (!dp[i][j])
        continue;

      for (auto it : Q[i])
        if (!(j >> dub[it] & 1))
          dp[fin_list[it]][j | (1<<dub[it])] = 1;
    }
  }

  REP(j, (1<<k))
    if (dp[vr][j])
      return 1;

  return 0;
}

int main()
{
  scanf("%d%d", &n, &k);

  if (k * k >= n) {
    printf("DA\n");
    return 0;
  }

  REP(i, n-1) {
    int a, b;
    scanf("%d%d", &a, &b); a--; b--;
    V[a].push_back(b);
    V[b].push_back(a);
  }

  dub[0] = -1;
  dfs(0, -1);
  
  printf("%s\n", rijesi() ? "DA" : "NE");

  return 0;
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
burza.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%d%d", &a, &b); a--; b--;
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 852 KB Output is correct
2 Correct 36 ms 2476 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 964 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 56 ms 2716 KB Output is correct
2 Correct 36 ms 2560 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 57 ms 2884 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 46 ms 2824 KB Output is correct
2 Correct 42 ms 2448 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 840 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1312 KB Output is correct
2 Correct 55 ms 3204 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2268 KB Output is correct
2 Correct 45 ms 2884 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 852 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2668 KB Output is correct
2 Correct 45 ms 2652 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 836 KB Output is correct
6 Correct 1 ms 716 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3008 KB Output is correct
2 Correct 47 ms 2692 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 54 ms 3156 KB Output is correct
6 Correct 1 ms 836 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1164 KB Output is correct
2 Correct 46 ms 2640 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 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 4 ms 708 KB Output is correct
2 Correct 56 ms 2932 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 972 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1600 KB Output is correct
2 Correct 56 ms 2932 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 21 ms 1604 KB Output is correct
6 Correct 1 ms 596 KB Output is correct