Submission #607774

#TimeUsernameProblemLanguageResultExecution timeMemory
607774Soul234Burza (COCI16_burza)C++14
160 / 160
58 ms3276 KiB
#include<bits/stdc++.h> using namespace std; void DBG() { cerr << "]\n"; } template<class H, class... T> void DBG(H h, T... t) { cerr << h; if(sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif // LOCAL #define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--) #define R0F(i,a) ROF(i,0,a) #define each(e,a) for(auto &e : (a)) #define sz(v) (int)(v).size() #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pb push_back #define tcT template<class T #define nl "\n" using ll = long long; using vi = vector<int>; using pi = pair<int,int>; using str = string; tcT> using V = vector<T>; tcT> using pqg = priority_queue<T,vector<T>,greater<T>>; void setIO(string NAME = "") { cin.tie(0)->sync_with_stdio(0); if(sz(NAME)) { freopen((NAME + ".inp").c_str(),"r",stdin); freopen((NAME + ".out").c_str(),"w",stdout); } } constexpr bool onbit(int x, int i) { return x>>i&1; } tcT> bool ckmin(T&a, const T&b) { return b < a ? a=b,1 : 0; } tcT> bool ckmax(T&a, const T&b) { return b > a ? a=b,1 : 0; } const int MOD = 1e9 + 7; const int MX = 4e2+5; int N, K, tin[MX], tout[MX], dep[MX], tt; vi adj[MX], lst[MX]; bool dp[MX][1<<20]; void dfs(int u, int p) { if(~p) dep[u] = dep[p] + 1; if(dep[u] == K) { tin[u] = tt++; tout[u] = tt; return; } tin[u] = tt; each(v, adj[u]) if(v != p) { dfs(v, u); } tout[u] = tt; } void solve() { cin>>N>>K; F0R(i,N-1) { int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } if(K*K >= N) { cout << "DA\n"; return; } memset(tin, -1, sizeof tin); dep[1] = 0; dfs(1, -1); FOR(i,2,N+1) if(~tin[i]) lst[tin[i]].pb(i); dp[0][0] = 1; F0R(i, tt) { F0R(msk, 1<<K) if(dp[i][msk]) { each(v, lst[i]) if(!onbit(msk, dep[v]-1)) { dp[tout[v]][msk|(1<<(dep[v]-1))] = 1; } } } bool ok = false; F0R(msk, 1<<K) ok |= dp[tt][msk]; if(ok) cout << "DA\n"; else cout << "NE\n"; } int main() { setIO(); int t=1; //cin>>t; while(t-->0) { solve(); } return 0; }

Compilation message (stderr)

burza.cpp: In function 'void setIO(std::string)':
burza.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...