Submission #1208939

#TimeUsernameProblemLanguageResultExecution timeMemory
1208939dksnfjkfnwkfwCat in a tree (BOI17_catinatree)C++20
51 / 100
36 ms35912 KiB
///*** Sown_Vipro ***/// /// ->TEAM SELECTION TEST<- /// #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("popcnt") #define F first #define S second #define pb push_back #define pi pair<int, int> #define pii pair<int, pair<int, int> > #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = a; i >= b; --i) #define all(s) s.begin(), s.end() #define szz(s) int(s.size()) const string NAME = "office"; const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7; void maxi(int &x, int y){ if(x < y) x = y; } void mini(int &x, int y){ if(x > y) x = y; }; void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); }; int n, k; vector<int> e[N]; namespace sub1{ int dp[5005][5005], f[5005], res; void dfs(int u, int p){ dp[u][0] = 1; // cout << u << "\n"; for(int v : e[u]){ if(v == p) continue; dfs(v, u); REP(i, k, 0) f[i] = dp[u][i]; REP(i, k, 0){ // cout << u << " " << v << " " << i << " " << f[i] << " " << dp[v][k - i - 1] << "\n"; dp[u][min(i, k - i)] = max(dp[u][min(i, k - i)], f[i] + dp[v][k - i - 1]); if(i * 2 >= k) dp[u][i] = max(dp[u][i], f[i] + dp[v][i - 1]); dp[u][i] = max(dp[u][i], dp[v][i - 1]); } REP(i, k, 0){ dp[u][i] = max(dp[u][i], dp[u][i + 1]); res = max(res, dp[u][i]); // cout << u << " " << i << " " << dp[u][i] << "\n"; } } } void solve(){ dfs(1, 0); cout << res; // cerr << res << "\n"; } } namespace sub2{ int dp[N][2], res; void dfs(int u, int p){ dp[u][1] = 1; for(int v : e[u]){ if(v == p) continue; dfs(v, u); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } res = max({res, dp[u][0], dp[u][1]}); } void solve(){ dfs(1, 0); cout << res; } } void solve(){ cin >> n >> k; FOR(i, 2, n){ int p; cin >> p; ++p; e[p].pb(i); e[i].pb(p); // int u, v; cin >> u >> v; // e[u].pb(v); // e[v].pb(u); } if(n <= 5000 && k <= 5000){ sub1::solve(); } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen((NAME + ".inp").c_str(), "r")){ freopen((NAME + ".inp").c_str(), "r", stdin); freopen((NAME + ".out").c_str(), "w", stdout); } int t = 1; // cin >> t; while(t--){ solve(); } }

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         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...