제출 #129499

#제출 시각아이디문제언어결과실행 시간메모리
129499antimirage친구 (IOI14_friend)C++14
0 / 100
3 ms632 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 = 1005; vector <int> g[N]; int u[N], dp[N][2], ans; int bfs (int v) { int res = 0; queue <int> q; q.push(v); while (!q.empty() ) { v = q.front(); q.pop(); res = max(res, dp[v][0]); res = max(res, dp[v][1]); for (auto to : g[v]) { if (u[to]) continue; dp[to][0] += max(dp[v][1], dp[v][0]); dp[to][1] += dp[v][0]; u[to] = 1; q.push(to); } } return res; } 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...