oj.uz

답안 #160027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160027 2019-10-25T17:36:10 Z rama_pang 친구 (IOI14_friend) C++14
58 / 100
 38 ms 3576 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], confidence[i]), alternate[v] = alternate[v] + alternate[i]

    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]], 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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 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 372 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 252 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 Incorrect 2 ms 376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 2 ms 380 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 #3
8.0 / 8.0

# 결과 실행 시간 메모리 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 380 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 4 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 368 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 3 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

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 340 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 3 ms 276 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 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 3 ms 376 KB Output is correct

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 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 Incorrect 38 ms 3576 KB Output isn't correct
13 Halted 0 ms 0 KB -