Submission #129507

#TimeUsernameProblemLanguageResultExecution timeMemory
129507antimirageFriend (IOI14_friend)C++14
0 / 100
8 ms5368 KiB
#include "friend.h" //#include "grader.cpp" #include <bits/stdc++.h> #define fr first #define sc second #define mk make_pair #define pb push_back #define all(s) s.begin(), s.end() using namespace std; const int N = 1e5 + 5; vector <int> g[N], vec; int u[N], dp[N][2], ans; int bfs (int v) { int start = v; vec.clear(); queue <int> q; q.push(v); u[v] = 1; while (!q.empty() ) { v = q.front(); q.pop(); vec.pb(v); for (auto to : g[v]) { if (u[to]) continue; u[to] = u[v] + 1; q.push(to); } } reverse(all(vec)); for (auto it : vec) { v = it; for (auto to : g[v]) { if (u[to] > u[v]) { assert(u[to] - 1 == u[v]); dp[v][1] += dp[to][0]; dp[v][0] += max(dp[to][1], dp[to][0]); } } } return max(dp[start][0], dp[start][1]); } int findSample(int n, int val[], int batya[], int type[]) { assert(val[0] == 1); dp[0][1] = 1; for (int i = 1; i < n; i++) { dp[i][1] = 1; assert(val[i] == 1); if (type[i] == 0) { g[batya[i]].pb(i); g[i].pb(batya[i]); } else if (type[i] == 1) { for (auto it: g[batya[i]]) { g[i].pb(it); g[it].pb(i); } } else assert(0); } for (int i = 0; i < n; i++) { if (u[i]) continue; ans += bfs(i); } return ans; }
#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...