제출 #441749

#제출 시각아이디문제언어결과실행 시간메모리
441749training4usacoBurza (COCI16_burza)C++11
0 / 160
10 ms9164 KiB
#include <iostream> #include <vector> using namespace std; int n, k; vector<vector<int>> adj; vector<vector<int>> newadj; // ignore nodes deeper than k vector<int> depth; vector<vector<int>> parents; int timer = 0; vector<int> sttime; vector<int> fntime; vector<int> loc; vector<int> dp (1 << 21); bool depthCheck(int v, int p) { if(depth[v] == k) { return true; } bool ret = false; for(auto next : adj[v]) { if(next == p) { continue; } depth[next] = depth[v] + 1; bool option = depthCheck(next, v); ret |= option; if(option) { newadj[v].push_back(next); } } return ret; } void dfs(int v, int p) { parents[v][0] = v; parents[v][1] = p; if(p != -1) { for(int i = 2; i <= depth[v] + 1; ++i) { // parent of parents[v][i - 1] = parents[v][i] parents[v][i] = parents[parents[v][i - 1]][1]; } } ++timer; cout << "v, p, timer: " << v << ", " << p << ", " << timer << endl; sttime[v] = timer; loc[timer] = v; for(int next : newadj[v]) { if(next != p) { dfs(next, v); } } fntime[v] = timer; } int main() { cin >> n >> k; if(k > 20) { cout << "DA" << endl; return 0; } adj = vector<vector<int>>(n + 1); newadj = vector<vector<int>>(n + 1); depth = vector<int>(n + 1, 0); parents = vector<vector<int>>(n + 1, vector<int>(n + 1, -1)); sttime = vector<int>(n + 1); fntime = vector<int>(n + 1); loc = vector<int>(n + 1); for(int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } if(!depthCheck(1, -1)) { // graph is too shallow cout << "DA" << endl; return 0; } dfs(1, -1); // cout << endl; // for (int i = 1; i <= n; i++) { // cout << i << ": " << sttime[i] << " " << fntime[i] << endl; // } for(int mask = 0; mask < (1 << k); ++mask) { int res = dp[mask]; while(res <= timer && depth[loc[res]] < k) { ++res; } if(res > timer) { cout << "DA" << endl; return 0; } int v = loc[res]; for(int i = 0; i < k; ++i) { if(mask && (1 << i)) { continue; } int p = parents[v][k - (i + 1)]; dp[mask | (1 << i)] = max(dp[mask | (1 << i)], fntime[p] + 1); } } cout << "NE" << endl; }

컴파일 시 표준 에러 (stderr) 메시지

burza.cpp: In function 'int main()':
burza.cpp:109:27: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
  109 |             if(mask && (1 << i)) {
      |                        ~~~^~~~~
#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...