| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1143644 | Rufat | Friend (IOI14_friend) | C++20 | 0 ms | 0 KiB |
// Global variable to store the best total so far.
int best;
// dp: from a given bitmask of vertices still “active” we record an upper bound.
unordered_map<uint64_t,int> memo;
// rec( mask, cur ) = try to complete an independent set starting from
// the set 'mask' (of vertices still available) having already total weight 'cur'
void rec(uint64_t mask, int cur, const vector<int>& weight,
const vector<uint64_t>& nbr) {
if(mask==0) {
best = max(best, cur);
return;
}
// Use memoization to prune
if(memo.count(mask) && memo[mask] + cur <= best) return;
// Choose a vertex v from mask (say, the least–significant one)
int v = __builtin_ctzll(mask);
// Option 1: take vertex v.
uint64_t mask2 = mask & ~(1ULL << v) & ~nbr[v]; // remove v and its neighbours
rec(mask2, cur + weight[v], weight, nbr);
// Option 2: do not take vertex v.
rec(mask & ~(1ULL << v), cur, weight, nbr);
memo[mask] = best - cur; // record an upper bound for mask
}
// The function to be implemented.
int findSample(int n, int confidence[], int host[], int protocol[]) {
// Build the graph.
// For each vertex we will compute a bitmask of its neighbours.
// We assume n is small enough (say n<=64) so that we can use a 64–bit integer.
vector<uint64_t> nbr(n, 0ULL);
// At stage 0, person 0 is in the network.
// We also keep, for each vertex, the set of its current friends.
vector< set<int> > friends(n);
// Note: confidence[i] is the weight of vertex i.
vector<int> weight(n);
for (int i = 0; i < n; i++)
weight[i] = confidence[i];
// Process stages 1 .. n–1:
for (int i = 1; i < n; i++) {
int h = host[i]; // host of stage i
int p = protocol[i]; // protocol code: 0, 1, or 2
if(p == 0) {
// IAmYourFriend: add edge (i, h)
friends[i].insert(h);
friends[h].insert(i);
} else if(p == 1) {
// MyFriendsAreYourFriends: add, for every friend f of h, edge (i, f)
for (int f : friends[h]) {
friends[i].insert(f);
friends[f].insert(i);
}
} else if(p == 2) {
// WeAreYourFriends: add edge (i, h) and for every friend f of h, edge (i, f)
friends[i].insert(h);
friends[h].insert(i);
for (int f : friends[h]) {
friends[i].insert(f);
friends[f].insert(i);
}
}
// (Optionally, you could also update a "host–tree" structure but here we only need the graph.)
}
// Now fill in the neighbour bitmasks.
for (int i = 0; i < n; i++){
for (int j : friends[i]) {
// (We assume that 0 <= j < n.)
nbr[i] |= (1ULL << j);
}
}
// Now solve the maximum–weight independent set by recursion.
best = 0;
memo.clear();
// Initially all vertices are available: mask = (1<<n)-1.
uint64_t all = (n==64 ? ~0ULL : ((1ULL << n) - 1));
rec(all, 0, weight, nbr);
return best;
}