제출 #810290

#제출 시각아이디문제언어결과실행 시간메모리
810290Kerim친구 (IOI14_friend)C++17
69 / 100
21 ms4436 KiB
#include "friend.h" #include "bits/stdc++.h" #define pb(x) push_back(x) using namespace std; const int N = 1005; vector<int> adj[N]; void add_edge(int u, int v){ adj[u].pb(v); adj[v].pb(u); } int dp[N][2]; void dfs(int nd, int pr, int val[]){ dp[nd][1] = val[nd]; dp[nd][0] = 0; for (auto c: adj[nd]){ if (c == pr) continue; dfs(c, nd, val); dp[nd][1] += dp[c][0]; dp[nd][0] += max(dp[c][0], dp[c][1]); } } int vis[N], col[N], matched[N]; void dfs0(int nd, vector<int>&L, vector<int> &R){ vis[nd] = 1; if (!col[nd]) L.pb(nd); else R.pb(nd); for (auto to: adj[nd]) if (!vis[to]){ col[to] = col[nd] ^ 1; dfs0(to, L, R); } } bool dfs1(int nd){ if (vis[nd]) return 0; vis[nd] = 1; for (auto x: adj[nd]){ if (matched[x] == -1 or dfs1(matched[x])){ matched[x] = nd; return 1; } } return 0; } const int MAXN = 1e5+5; int p[MAXN], q[MAXN]; int findSample(int n,int arr[],int host[],int protocol[]){ for (int i = 0; i < n; i++) adj[i].clear(); bool subtask1 = (n <= 10); bool subtask2 = true, subtask3 = true; bool subtask4 = true, subtask5 = true; // Build graph for (int i = 1; i < n; i++){ int v = host[i], p = protocol[i]; subtask4 &= (p == 0); subtask2 &= (p == 1); subtask3 &= (p == 2); subtask5 &= (p <= 1); } if (n <= 1000){ for (int i = 1; i < n; i++){ int v = host[i], p = protocol[i]; if (p == 0)//IAmYourFriend add_edge(v, i); else if(p == 1){//MyFriendsAreYourFriends for (auto to: adj[v]) add_edge(to, i); } else{//WeAreYourFriends for (auto to: adj[v]) add_edge(to, i); add_edge(v, i); } } } int answer = 0; if (subtask1){ for (int mask = 0; mask < (1<<n); mask++){ bool bad = 0; int sum = 0; for (int i = 0; i < n; i++) if (mask>>i&1){ sum += arr[i]; for (auto to: adj[i]) bad |= (mask>>to&1); } if (!bad) answer = max(answer, sum); } } else if(subtask2){ for (int i = 0; i < n; i++) answer += arr[i]; } else if (subtask3){ for (int i = 0; i < n; i++) answer = max(answer, arr[i]); } else if (subtask4){ dfs(0, -1, arr); answer = max(dp[0][0], dp[0][1]); } else if(subtask5){ for (int i = 0; i < n; i++) vis[i] = col[i] = 0; int MM = 0; for (int i = 0; i < n; i++) if (!vis[i]){ vector<int> L, R; dfs0(i, L, R); // Kuhn's algorithm for (auto x: R) matched[x] = -1; for (auto x: L){ for (auto y: L) vis[y] = false; dfs1(x); } for (auto x: R) MM += (matched[x] != -1); } answer = n - MM; } else{ // puts("subtask6"); for (int i = 0; i < n; i++) p[i] = arr[i], q[i] = 0; for (int i = n-1; i > 0; i--){ int pp = protocol[i]; int v = host[i]; if (pp == 2){ //WeAreYourFriends p[v] = max(p[v] + q[i], p[i] + q[v]); q[v] = q[v] + q[i]; } else if (pp == 1){//MyFriendsAreYourFriends p[v] = max(p[v]+p[i], max(p[v] + q[i], p[i] + q[v])); q[v] = q[v] + q[i]; } else{//IamYourFriend p[v] = p[v] + q[i]; q[v] = max(p[i] + q[v], q[v] + q[i]); } // cout<<i<<"->"<<v<<": "<<p[v]<<" "<<q[v]<<endl; } answer = max(p[0], q[0]); } return answer; }

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

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:60:7: warning: unused variable 'v' [-Wunused-variable]
   60 |   int v = host[i], p = protocol[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...