# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
166991 | 2019-12-05T07:03:47 Z | davitmarg | 친구 (IOI14_friend) | C++17 | 3 ms | 380 KB |
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000009ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() using namespace std; #ifndef death #include "friend.h" #endif const int N = 1003; int dp[N][2], a[N]; vector<int> g[N]; void dfs(int v, int p) { dp[v][1] = a[v]; for (int i = 0; i < g[v].size(); i++) { int to = g[v][i]; if (to == p) continue; dfs(to, v); dp[v][1] += dp[to][0]; dp[v][0] += max(dp[to][1], dp[to][0]); } } int findSample(int n, int confidence[], int host[], int protocol[]) { int ans = 0; set<int> type; for (int i = 1; i < n; i++) type.insert(protocol[i]); for (int i = 0; i < n; i++) a[i] = confidence[i]; if (n <= 10) { for (int i = 1; i < n; i++) { if (protocol[i] != 2) { g[host[i]].PB(i); g[i].PB(host[i]); } if (protocol[i] != 1) for (int j = 0; j < g[host[i]].size(); j++) { g[g[host[i]][j]].PB(i); g[i].PB(g[host[i]][j]); } } for (int mask = 0; mask < (1 << n); mask++) { bool norm = 1; int sum = 0; for (int i = 0; i < n; i++) { if (((1 << i) & mask) == 0) continue; sum += a[i]; for (int j = 0; j < g[i].size(); j++) { int to = g[i][j]; if ((1 << to) & mask) { norm = 0; break; } } } if (norm) ans = max(ans, sum); } return ans; } if (type.size() == 1) { if ((*type.begin()) == 2) { sort(confidence, confidence + n); ans = confidence[n - 1]; } else if ((*type.begin()) == 1) { for (int i = 0; i < n; i++) ans += a[i]; } else { for (int i = 1; i < n; i++) { g[host[i]].PB(i); g[i].PB(host[i]); } dfs(0, -1); ans = max(dp[0][1], dp[0][0]); } } return ans; } #ifdef death int main() { return 0; } #endif /* 7 5 6 7 1 2 3 4 7 5 6 7 1 2 10 4 7 2 3 4 9 6 7 1 1 2 3 4 9 6 7 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 248 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Incorrect | 2 ms | 376 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |