제출 #920828

#제출 시각아이디문제언어결과실행 시간메모리
920828rxlfd314친구 (IOI14_friend)C++17
46 / 100
168 ms48160 KiB
#include "friend.h" #include <bits/stdc++.h> using namespace std; using ari2 = array<int, 2>; #define vt vector #define size(x) (int((x).size())) #define all(x) begin(x), end(x) #define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d)) #define FOR(a, b, c) REP(a, b, c, 1) #define ROF(a, b, c) REP(a, b, c, -1) int findSample(int N, int *C, int *H, int *P){ if (accumulate(P+1, P+N, 0) == N-1<<1) { vt<vt<int>> adj(N); FOR(i, 1, N-1) { adj[i].push_back(H[i]); adj[H[i]].push_back(i); } vt<bool> seen(N); int ans = 0; FOR(ii, 0, N-1) { if (seen[ii]) continue; int mx = 0; queue<int> qu; qu.push(ii); seen[ii] = true; while (size(qu)) { int i = qu.front(); qu.pop(); mx = max(mx, C[i]); for (int j : adj[i]) if (!seen[j]) seen[j] = true, qu.push(j); } ans += mx; } return ans; } if (*max_element(P+1, P+N) == 1 && *min_element(P+1, P+N) == 1) return accumulate(C, C+N, 0); if (*max_element(P+1, P+N) == 0) { vt<vt<int>> adj(N); FOR(i, 1, N-1) adj[H[i]].push_back(i); vt<ari2> dp(N, {0, 0}); function<void(int)> dfs = [&](int i) { dp[i][1] = C[i]; for (int j : adj[i]) { dfs(j); dp[i][0] += max(dp[j][0], dp[j][1]); dp[i][1] += dp[j][0]; } }; dfs(0); return max(dp[0][0], dp[0][1]); } if (N <= 10) { vt<vt<bool>> adj(N, vt<bool>(N)); FOR(i, 1, N-1) { if (!(P[i] & 1)) adj[i][H[i]] = adj[H[i]][i] = true; if (P[i]) FOR(j, 0, N-1) if (adj[H[i]][j] && i != j && j != H[i]) adj[i][j] = adj[j][i] = true; } vt<int> dp(1<<N, INT_MIN); dp[0] = 0; int ans = 0; FOR(bm, 1, (1<<N)-1) { int i = __builtin_ctz(bm); for (int j = bm; j; j &= j - 1) if (adj[i][__builtin_ctz(j)]) goto jail; if (dp[bm^1<<i] > INT_MIN) ans = max(ans, dp[bm] = dp[bm^1<<i] + C[i]); jail:; } return ans; } vt<vt<int>> adj(N); vt<bool> type(N); FOR(i, 1, N-1) { if (P[i]) for (int j : adj[H[i]]) adj[j].push_back(i), adj[i].push_back(j); else adj[i].push_back(H[i]), adj[H[i]].push_back(i); if (size(adj[i])) type[i] = type[adj[i][0]] ^ 1; } int ans = 0; vt<bool> seen(N); FOR(ii, 0, N-1) { if (seen[ii]) continue; ari2 cnt = {0, 0}; function<void(int)> dfs = [&](int i) { if (seen[i]) return; cnt[type[i]]++; seen[i] = true; for (int j : adj[i]) dfs(j); }; dfs(ii); ans += max(cnt[0], cnt[1]); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:15:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   15 |   if (accumulate(P+1, P+N, 0) == N-1<<1) {
      |                                  ~^~
#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...