Submission #1143644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143644		Rufat	친구 (IOI14_friend)	C++20	Compilation error	0 ms	0 KiB

friend

// 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;
}

Compilation message (stderr)

friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
    5 | unordered_map<uint64_t,int> memo;
      |               ^~~~~~~~
friend.cpp:1:1: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
  +++ |+#include <cstdint>
    1 | // Global variable to store the best total so far.
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
    5 | unordered_map<uint64_t,int> memo;
      |               ^~~~~~~~
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:15: error: 'uint64_t' was not declared in this scope
friend.cpp:5:15: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:5:1: error: 'unordered_map' does not name a type
    5 | unordered_map<uint64_t,int> memo;
      | ^~~~~~~~~~~~~
friend.cpp:9:6: error: variable or field 'rec' declared void
    9 | void rec(uint64_t mask, int cur, const vector<int>& weight,
      |      ^~~
friend.cpp:9:10: error: 'uint64_t' was not declared in this scope
    9 | void rec(uint64_t mask, int cur, const vector<int>& weight,
      |          ^~~~~~~~
friend.cpp:9:10: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:9:25: error: expected primary-expression before 'int'
    9 | void rec(uint64_t mask, int cur, const vector<int>& weight,
      |                         ^~~
friend.cpp:9:34: error: expected primary-expression before 'const'
    9 | void rec(uint64_t mask, int cur, const vector<int>& weight,
      |                                  ^~~~~
friend.cpp:10:10: error: expected primary-expression before 'const'
   10 |          const vector<uint64_t>& nbr) {
      |          ^~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:36:12: error: 'uint64_t' was not declared in this scope
   36 |     vector<uint64_t> nbr(n, 0ULL);
      |            ^~~~~~~~
friend.cpp:36:12: note: 'uint64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
friend.cpp:36:5: error: 'vector' was not declared in this scope
   36 |     vector<uint64_t> nbr(n, 0ULL);
      |     ^~~~~~
friend.cpp:36:22: error: 'nbr' was not declared in this scope
   36 |     vector<uint64_t> nbr(n, 0ULL);
      |                      ^~~
friend.cpp:39:13: error: 'set' was not declared in this scope
   39 |     vector< set<int> > friends(n);
      |             ^~~
friend.cpp:39:17: error: expected primary-expression before 'int'
   39 |     vector< set<int> > friends(n);
      |                 ^~~
friend.cpp:41:12: error: expected primary-expression before 'int'
   41 |     vector<int> weight(n);
      |            ^~~
friend.cpp:43:9: error: 'weight' was not declared in this scope
   43 |         weight[i] = confidence[i];
      |         ^~~~~~
friend.cpp:51:13: error: 'friends' was not declared in this scope
   51 |             friends[i].insert(h);
      |             ^~~~~~~
friend.cpp:55:26: error: 'friends' was not declared in this scope
   55 |             for (int f : friends[h]) {
      |                          ^~~~~~~
friend.cpp:61:13: error: 'friends' was not declared in this scope
   61 |             friends[i].insert(h);
      |             ^~~~~~~
friend.cpp:72:22: error: 'friends' was not declared in this scope
   72 |         for (int j : friends[i]) {
      |                      ^~~~~~~
friend.cpp:80:5: error: 'memo' was not declared in this scope
   80 |     memo.clear();
      |     ^~~~
friend.cpp:82:13: error: expected ';' before 'all'
   82 |     uint64_t all = (n==64 ? ~0ULL : ((1ULL << n) - 1));
      |             ^~~~
      |             ;
friend.cpp:83:9: error: 'all' was not declared in this scope
   83 |     rec(all, 0, weight, nbr);
      |         ^~~
friend.cpp:83:17: error: 'weight' was not declared in this scope
   83 |     rec(all, 0, weight, nbr);
      |                 ^~~~~~
friend.cpp:83:5: error: 'rec' was not declared in this scope
   83 |     rec(all, 0, weight, nbr);
      |     ^~~