Submission #465925

#TimeUsernameProblemLanguageResultExecution timeMemory
465925YuisuyunoBurza (COCI16_burza)C++14
160 / 160
12 ms1408 KiB
//Nguyen Huu Hoang Minh #include <bits/stdc++.h> #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define reset(x) memset(x, 0,sizeof(x)) #define pb push_back #define mp make_pair #define fi first #define se second #define N 405 #define remain(x) if (x > MOD) x -= MOD #define ii pair<int, int> #define iiii pair< ii , ii > #define viiii vector< iiii > #define vi vector<int> #define vii vector< ii > #define bit(x, i) (((x) >> (i)) & 1) #define Task "test" #define int long long using namespace std; typedef long double ld; const int inf = 1e10; const int minf = -1e10; int n, k; vector<int> g[N]; int dp[1<<20]; int d[N]; ii resp[N]; int par[N][20]; int cnt; void readfile() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); if (fopen(Task".inp","r")) { freopen(Task".inp","r",stdin); //freopen(Task".out","w",stdout); } cin >> n >> k; if (k*k >= n){ cout << "DA"; exit(0); } for(int i=1; i<n; i++){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } } void dfs(int u, int pre){ if (d[u]==k){ resp[u] = {cnt,cnt}; cnt++; return; } resp[u].fi = cnt; for(auto v : g[u]){ if (v!=pre){ d[v] = d[u]+1; dfs(v,u); resp[u].se = cnt-1; } } } void proc() { for(int i=1; i<=n; i++) resp[i] = ii(0,-1); d[1] = 0; dfs(1,0); //for(int i=1; i<=n; i++) cout << i << ' ' << resp[i].fi << ' ' << resp[i].se << endl; for(int i=1; i<=n; i++){ par[resp[i].fi][d[i]-1]=max(par[resp[i].fi][d[i]-1],resp[i].se+1); } for(int i=1; i<20; i++){ for(int j=1; j<=cnt+1; j++){ par[j][i] = max(par[j][i],par[j-1][i]); } } for(int i=0; i<(1<<k); i++){ for(int j=0; j<k; j++){ if (!(i&(1<<j))) dp[i^(1<<j)] = max(dp[i^(1<<j)],par[dp[i]][j]); } } if (dp[(1<<k)-1]==cnt)cout <<"DA"; else cout << "NE"; } signed main() { readfile(); proc(); return 0; }

Compilation message (stderr)

burza.cpp: In function 'void readfile()':
burza.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...