Submission #684126

#TimeUsernameProblemLanguageResultExecution timeMemory
684126Red_InsideBurza (COCI16_burza)C++17
160 / 160
206 ms210912 KiB
#include <bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back #define mp make_pair #define o cout<<"BUG"<<endl; #define FOR(i, j, n) for(int j = i; j < n; ++j) #define forn(i, j, n) for(int j = i; j <= n; ++j) #define nfor(i, j, n) for(int j = n; j >= i; --j) #define all(v) v.begin(), v.end() #define ld long double #define ull unsigned long long using namespace std; const int maxn=400+10,LOG=17,mod=1e9+7; int block = 0, timer = 0; const double eps = 1e-9; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define bt(i) (1 << (i)) //#define int ll const int inf=1e9; #define y1 yy #define prev pre #define pii pair <int, int> int n, cnt, t, del[maxn], ok[maxn][maxn], L[maxn], R[maxn], lf[maxn], rf[maxn]; int dp[1100000][410]; vector <int> edge[maxn]; int dfs(int v, int pred = -1, int deep = 0) { if(deep > t) del[v] = 1; int mx = deep; for(auto to : edge[v]) { if(to == pred) continue; int ret = dfs(to, v, deep + 1); mx = max(mx, ret); } if(mx < t) del[v] = 1; return mx; } void dfs2(int v, int pred = -1, int deep = 0) { for(auto to : edge[v]) { if(to == pred) continue; dfs2(to, v, deep + 1); if(lf[v] == 0) lf[v] = lf[to]; rf[v] = rf[to]; } if(deep == t) { cnt++; lf[v] = cnt; rf[v] = cnt; } forn(lf[v], i, rf[v]) { ok[i][deep] = max(ok[i][deep], rf[v]); } } main() { cin >> n >> t; forn(1, i, n - 1) { int l, r; cin >> l >> r; edge[l].pb(r); edge[r].pb(l); L[i] = l; R[i] = r; } dfs(1); vector <int> vec; forn(1, i, n) { if(!del[i]) vec.pb(i); } forn(1, i, n) edge[i].clear(); forn(1, i, n-1) { if(!del[L[i]] && !del[R[i]]) { L[i] = lower_bound(all(vec), L[i]) - vec.begin() + 1; R[i] = lower_bound(all(vec), R[i]) - vec.begin() + 1; edge[L[i]].pb(R[i]); edge[R[i]].pb(L[i]); } } n = (int)vec.size(); if(t * t >= n) { cout << "DA"; return 0; } dfs2(1); dp[0][1] = 1; forn(1, i, cnt) { forn(0, mask, (1 << t) - 1) { if(!dp[mask][i]) continue; // cout << mask << " " << i << endl; forn(1, j, t) { if(!((mask>>(j-1))&1) && ok[i][j] != 0) { dp[(mask | (1 << (j - 1)))][ok[i][j] + 1] = 1; } } } } if(dp[(1<<t)-1][cnt+1]) cout << "DA"; else cout << "NE"; }

Compilation message (stderr)

burza.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main()
      | ^~~~
#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...