제출 #492048

#제출 시각아이디문제언어결과실행 시간메모리
492048davi_bart친구 (IOI14_friend)C++14
35 / 100
11 ms7508 KiB
#include "friend.h" #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long // #define int ll #define fi first #define se second #define ld long double #define pb push_back mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); set<int> v[100010]; vector<bool> vis(100010, 0); vector<int> figli[100010]; void dfs(int pos, int par) { if (vis[pos]) return; vis[pos] = 1; if (par != -1) figli[par].pb(pos); for (int x : v[pos]) dfs(x, pos); } int memo[100010][2]; vector<int> conf; int sol(int pos, bool posso) { if (memo[pos][posso] && pos != 100005) return memo[pos][posso]; int ans = conf[pos]; for (int x : figli[pos]) { for (int y : figli[x]) { int k = sol(y, 0); int o = 0; for (int z : figli[y]) { int u = 0; if (v[pos].count(z) == 0) { u = sol(z, 1); } int l = 0; for (int w : figli[z]) { l += sol(w, 1); } o += max(u, l); } ans += max(k, o); } } if (posso) { int k = 0; for (int x : figli[pos]) { k += sol(x, 1); } ans = max(ans, k); } return memo[pos][posso] = ans; } int findSample(int N, int confidence[], int host[], int protocol[]) { for (int i = 0; i < N; i++) conf.pb(confidence[i]); int a[3] = {0, 0, 0}; for (int i = 1; i < N; i++) { a[protocol[i]]++; } if (a[1] == N - 1) { int tot = 0; for (int i = 0; i < N; i++) tot += confidence[i]; return tot; } if (a[2] == N - 1) { int tot = 0; for (int i = 0; i < N; i++) tot = max(confidence[i], tot); return tot; } for (int i = 1; i < N; i++) { if (protocol[i] == 1 || protocol[i] == 2) { for (int x : v[host[i]]) { v[x].insert(i); v[i].insert(x); } } if (protocol[i] == 0 || protocol[i] == 2) { v[host[i]].insert(i); v[i].insert(host[i]); } } int ans = 0; for (int i = 0; i < N; i++) { if (!vis[i]) { dfs(i, -1); int ma = sol(i, 1); // figli[100005].clear(); // figli[100005].pb(i); // ma = max(ma, sol(100005) - 1); ans += ma; } } 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...