oj.uz

Submission #23066

# Submission time Handle Problem Language Result Execution time Memory
23066 2017-05-02T14:55:20 Z model_code Burza (COCI16_burza) C++11
160 / 160
 63 ms 416764 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:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &k);
                        ^
burza.cpp:85:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a, &b); a--; b--;
                          ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 416764 KB Output is correct
2 Correct 43 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 416764 KB Output is correct
2 Correct 43 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 59 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 416764 KB Output is correct
2 Correct 39 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 416764 KB Output is correct
2 Correct 56 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 416764 KB Output is correct
2 Correct 43 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 416764 KB Output is correct
2 Correct 46 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 416764 KB Output is correct
2 Correct 46 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 59 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 416764 KB Output is correct
2 Correct 39 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 416764 KB Output is correct
2 Correct 53 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 0 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 416764 KB Output is correct
2 Correct 56 ms 416764 KB Output is correct
3 Correct 0 ms 416764 KB Output is correct
4 Correct 0 ms 416764 KB Output is correct
5 Correct 19 ms 416764 KB Output is correct
6 Correct 0 ms 416764 KB Output is correct