oj.uz

Submission #160028

# Submission time Handle Problem Language Result Execution time Memory
160028 2019-10-25T17:42:08 Z rama_pang Friend (IOI14_friend) C++14
100 / 100
 37 ms 3320 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;


/*  Protocols: add new vertex i at step i, with following types:
    1.  type 0 = IAmYourFriend : edge between vertex i and host[i]
    2.  type 1 = MyFriendsAreYourFriends : edge between vertex i and 
                 all friends of host[i], not includeing host[i]
    3.  type 2 = WeAreYourFriends : IAmYourFriend + MyFriendsAreYourFriends

    Answer is the maximum cost independent set. There are 3 cases for each protocols:
    1.  alternate[v] = alternate[v] + confidence[i], confidence[v] = confidence[v] + alternate[i]
    2.  confidence[v] = confidence[v] + confidence[i], alternate[v] = alternate[v] + alternate[i]
    3.  confidence[v] = max(confidence[v] + alternate[i], alternate[v] + confidence[i]), alternate[v] = alternate[v] + alternate[i]

    Then if alternate[v] > confidence[v], confidence[v] = alternate[v].

    Proof 1:
        Denote current graph as G. The solution for this graph is costG, before i is
        added to the graph (and this is true for the next proofs). There are two
        cases: either i is picked, or not. If i is picked, then v cannot be picked,
        and vice versa. Thus we can solve this problem by keeping another array
        alternate, denoting the cost if i is not picked.

    Proof 2:
        Denote current graph as G. The solution for this graph is costG, if v is not
        picked, or costG + confidence, if v is picked. Thus it is exactly the same as
        solving the graph G, with confidence[v] = confidence[v] + confidence[i].

    Proof 3:
        Denote current graph as G. Let the solution for this graph is costG. Then if 
        we pick v, the we cannot pick i. On the other hand, if we pick i, we cannot
        pick v. If we pick either i or v, then their neighbours couldn't be picked.
        So the optimal way is by max(i, v) or not picking it.Thus this is exactly the 
        same problem as finding costG with confidence[v] = max(confidence[v], confidence[i]).

    For the transition, just alternate between the array alternate and confidence. The answer
    is the maximum of alternate and confidence at vertex 0, after starting from the end of
    protocols added.

*/


int findSample(int n, int confidence_[], int host[], int protocol[]) {
    vector<int> confidence(n, 0), alternate(n, 0);
    for (int i = 0; i < n; i++) confidence[i] = confidence_[i];
    for (int i = n - 1; i > 0; i--) {
        switch (protocol[i]) {
        case 0: // IAmYourFriend
            confidence[host[i]]  = confidence[host[i]] + alternate[i];
            alternate[host[i]]   = alternate[host[i]] + confidence[i];
            break;
        case 1: // MyFriendsAreYourFriends
            confidence[host[i]]  = confidence[host[i]] + confidence[i];
            alternate[host[i]]   = alternate[host[i]] + alternate[i];
            break;
        case 2: // WeAreYourFriends
            confidence[host[i]]  = max(confidence[host[i]] + alternate[i], alternate[host[i]] + confidence[i]);
            alternate[host[i]]   = alternate[host[i]] + alternate[i];
            break;
        }

        confidence[host[i]] = max(confidence[host[i]], alternate[host[i]]);
    }

    return confidence[0];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 37 ms 2296 KB Output is correct
13 Correct 20 ms 1912 KB Output is correct
14 Correct 35 ms 3192 KB Output is correct
15 Correct 37 ms 3320 KB Output is correct