제출 #385854

#제출 시각아이디문제언어결과실행 시간메모리
385854ParsaAlizadeh친구 (IOI14_friend)C++17
27 / 100
33 ms1516 KiB
#include <bits/stdc++.h> #include "friend.h" using namespace std; int Sub1(int n, int confidence[], int host[], int protocol[]) { vector<vector<bool>> g(n, vector<bool>(n, false)); auto add_edge = [&g] (int u, int v) { g[u][v] = g[v][u] = true; }; for (int i = 1; i < n; i++) { if (protocol[i] == 0 || protocol[i] == 2) { add_edge(i, host[i]); } if (protocol[i] == 1 || protocol[i] == 2) { for (int j = 0; j < n; j++) if (g[host[i]][j]) { add_edge(j, i); } } } int ans = -1; for (int mask = 0; mask < (1 << n); mask++) { bool flag = true; int now = 0; for (int i = 0; i < n; i++) if (mask & (1 << i)) { now += confidence[i]; for (int j = i + 1; j < n; j++) if (mask & (1 << j)) { flag &= !g[i][j]; } } if (!flag) continue; ans = max(ans, now); } return ans; } int Sub2(int n, int confidence[], int host[], int protocol[]) { int ans = confidence[0]; for (int i = 1; i < n; i++) { if (protocol[i] != 1) return -1; ans += confidence[i]; } return ans; } int Sub3(int n, int confidence[], int host[], int protocol[]) { int ans = confidence[0]; for (int i = 1; i < n; i++) { if (protocol[i] != 2) return -1; ans = max(ans, confidence[i]); } return ans; } int Sub4(int n, int confidence[], int host[], int protocol[]) { for (int i = 1; i < n; i++) { if (protocol[i] != 0) return -1; } vector<vector<int>> adj(n), dp(n, vector<int>(2)); for (int i = 1; i < n; i++) adj[host[i]].push_back(i); for (int i = n; i--;) { dp[i][1] = confidence[i]; for (int j : adj[i]) { dp[i][0] += dp[i][1]; dp[i][1] += dp[i][0]; } dp[i][1] = max(dp[i][1], dp[i][0]); } return dp[0][1]; } int findSample(int n, int confidence[], int host[], int protocol[]){ int ans = -1; if (n <= 10) return Sub1(n, confidence, host, protocol); if ((ans = Sub2(n, confidence, host, protocol)) != -1) return ans; if ((ans = Sub3(n, confidence, host, protocol)) != -1) return ans; if ((ans = Sub4(n, confidence, host, protocol)) != -1) return ans; return -1; }

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

friend.cpp: In function 'int Sub4(int, int*, int*, int*)':
friend.cpp:67:12: warning: unused variable 'j' [-Wunused-variable]
   67 |   for (int j : adj[i]) {
      |            ^
#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...