Submission #918395

#TimeUsernameProblemLanguageResultExecution timeMemory
918395LudisseyBurza (COCI16_burza)C++14
0 / 160
2 ms600 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int LOG=10; vector<vector<int>> adj; vector<int> depth; vector<int> kthDepth; vector<vector<int>> parent; int k; int comf(int a){ return (((a+49)/50)-1); } vector<int> addNumb(int a, vector<int> mask){ int i=comf(a); mask[i]+=(1<<(a-(i*50))); return mask; } vector<int> optimal; bool compMask(vector<int> a, vector<int> b){ for (int i = 1; i <= 8; i++) { if(a[i]!=b[i]) return 0; } return 1; } map<int,map<vector<int>, int>> memo; bool dp(int d, vector<int> mask){ if(memo[d].find(mask)!=memo[d].end()) return memo[d][mask]; if(d==k) return compMask(mask, optimal); map<int,vector<int>> mp; int depthDf=k-d; for (int i = 0; i < kthDepth.size(); i++) { int u=kthDepth[i]; for (int j = LOG-1; j >= 0; j--) if(depthDf&(1<<j)) u=parent[u][j]; vector<int> empty(8,0); if(mp.find(u)==mp.end()){ mp[u]=empty; } empty=mp[u]; empty[comf(kthDepth[i])]=empty[comf(kthDepth[i])]+(1<<(kthDepth[i]-(comf(kthDepth[i])*50))); mp[u]=empty; } for (auto u : mp) { if(dp(d+1, u.second)) return memo[d][mask]=true; } if(mp.size()==0) return memo[d][mask]=true; return memo[d][mask]=false; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,K; cin >> n >> K; k=K; parent.resize(n+1, vector<int>(LOG)); parent[1][0]=1; adj.resize(n+1); depth.resize(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); } optimal.resize(8,0); queue<pair<int,int>> queue; vector<bool> visited(n+1); queue.push({1,0}); while(!queue.empty()){ int x=queue.front().first,d=queue.front().second; queue.pop(); depth[x]=d; if(d==K) { optimal=addNumb(x,optimal); kthDepth.push_back(x); } visited[x]=true; for (auto u : adj[x]) { if(visited[u]) continue; queue.push({u,d+1}); parent[u][0]=x; } } for (int i = 1; i <= n; i++) for (int j = 1; j < LOG; j++) parent[i][j]=parent[parent[i][j-1]][j-1]; vector<int> empty(8,0); bool DA=dp(0, empty); if(DA) cout << "DA\n"; else cout << "NE\n"; return 0; }

Compilation message (stderr)

burza.cpp: In function 'bool dp(long long int, std::vector<long long int>)':
burza.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < kthDepth.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
burza.cpp:46:51: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |         if(dp(d+1, u.second)) return memo[d][mask]=true;
burza.cpp:48:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   48 |     if(mp.size()==0) return memo[d][mask]=true;
burza.cpp:49:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   49 |     return memo[d][mask]=false;
#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...