| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 741715 | rominanafu | Friend (IOI14_friend) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> amigos[100005];
int confidence[100005];
bool vis[100005];
bool tomo[100005];
int tomo_no_tomo(int x, int &n) {
if (x == n)
return 0;
bool puedo_tomar = true;
int r=0;
for(auto a:amigos[x]) {
if (tomo[a]) {
puedo_tomar = false;
break;
}
}
if (puedo_tomar) {
tomo[x] = true;
r = tomo_no_tomo(x+1, n) + confidence[x];
tomo[x] = false;
}
r = max(r, tomo_no_tomo(x+1, n));
return r;
}
int findSample(int n, int c[], int host[], int protocol[]) {
int max_con = c[0];
int sub2 = 0;
confidence[0] = c[0];
for(int i=1; i<n; i++){
confidence[i] = c[i];
max_con += c[i];
if (protocol[i] == 0) { /// I Am Your Friend
amigos[i].push_back(host[i]);
amigos[host[i]].push_back(i);
} else if (protocol[i] == 1) { /// My Friends are Your Friends
sub2++;
for(auto e:amigos[host[i]]) {
amigos[i].push_back(e);
amigos[e].push_back(i);
}
} else { /// We Are Your Friends
amigos[i].push_back(host[i]);
amigos[host[i]].push_back(i);
for(auto e:amigos[host[i]]) {
amigos[i].push_back(e);
amigos[e].push_back(i);
}
}
}
if (sub2 != n-1) {
max_con = tomo_no_tomo(0, n);
}
// for(int i=0; i<n; i++) {
// cout << "amigos de " << i << " son: ";
// for(auto a:amigos[i])
// cout << a << ' ';
// cout << endl;
// }
return max_con; /// return maximum confidence possible
}