Submission #696999

#TimeUsernameProblemLanguageResultExecution timeMemory
696999Markomafko972Burza (COCI16_burza)C++14
0 / 160
146 ms4788 KiB
#include <bits/stdc++.h> #define X first #define Y second #define pb push_back #define pii pair<int, int> typedef long long ll; using namespace std; const int MOD = 1e9 + 7; const ll INF = 1e18; const int OFF = (1 << 20); const int MAXN = (1 << 20); int n, k, a, b; vector<int> v[405]; vector<int> e[30][30]; vector<int> br[30]; bool dp[2][MAXN]; void dfs(int x, int d, int p) { if (d > k) return; br[d].push_back(x); for (int i = 0; i < v[x].size(); i++) { if (v[x][i] != p) { e[d][(int)br[d].size()-1].push_back((int)br[d+1].size()); dfs(v[x][i], d+1, x); } } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> k; if (k > 20) { cout << "DA"; return 0; } for (int i = 0; i < n-1; i++) { cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } dfs(1, 0, 0); dp[0][0] = 1; for (int i = 0; i < k; i++) { for (int mask = 0; mask < (1 << ((int)br[i].size())); mask++) { if (dp[0][mask] == 0) continue; int nova = 0; for (int j = 0; j < br[i].size(); j++) { if ((mask&(1 << j)) == 0) continue; for (int slj = 0; slj < e[i][j].size(); slj++) nova |= (1 << e[i][j][slj]); } for (int j = 0; j < br[i+1].size(); j++) { dp[1][(nova|(1 << j))] = 1; } } for (int mask = 0; mask < (1 << ((int)br[i+1].size())); mask++) { dp[0][mask] = dp[1][mask]; dp[1][mask] = 0; } } if (dp[0][(1 << ((int)br[k].size()))-1] == 1) cout << "DA"; else cout << "NE"; return 0; }

Compilation message (stderr)

burza.cpp: In function 'void dfs(int, int, int)':
burza.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 0; i < v[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~
burza.cpp: In function 'int main()':
burza.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int j = 0; j < br[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~
burza.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int slj = 0; slj < e[i][j].size(); slj++) nova |= (1 << e[i][j][slj]);
      |                       ~~~~^~~~~~~~~~~~~~~~
burza.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int j = 0; j < br[i+1].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...