| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 742251 | 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];
bool vis[100005];
bool tomo[100005];
int c[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) + c[x];
tomo[x] = false;
}
r = max(r, tomo_no_tomo(x+1, n));
return r;
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
int max_con = confidence[0];
int m2 = confidence[0];
int, sub1 = 0, sub2 = 0, sub3 = 0;
c[0] = confidence[0];
for(int i=1; i<n; i++){
c[i] = confidence[i];
if (protocol[i] == 0) { /// I Am Your Friend
sub1++;
amigos[i].push_back(host[i]);
amigos[host[i]].push_back(i);
} else if (protocol[i] == 1) { /// My Friends are Your Friends
sub2++;
max_con += confidence[i];
for(auto e:amigos[host[i]]) {
amigos[i].push_back(e);
amigos[e].push_back(i);
}
} else { /// We Are Your Friends
sub3++;
m2 = max(m2, confidence[i]);
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 == 0 && sub1 == 0) {
max_con = m2;
} else if (sub1) {
max_con = tomo_no_tomo(0, n);
}
return max_con; /// return maximum confidence possible
}