oj.uz

답안 #500755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500755 2022-01-01T07:40:20 Z InternetPerson10 친구 (IOI14_friend) C++17
46 / 100
 21 ms 1428 KB 
#include "friend.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;

int findSample(int n, int confidence[], int host[], int protocol[]){
    int mip = 4, map = 0;
    for(int i = 1; i < n; i++) {
        mip = min(mip, protocol[i]);
        map = max(map, protocol[i]);
    }
    if(n <= 10) { // Subtask 1
        adj.resize(n);
        for(int i = 1; i < n; i++) {
            int x, y;
            if(protocol[i] == 0) {
                tie(x, y) = {i, host[i]};
                adj[x].push_back(y);
                adj[y].push_back(x);
            }
            if(protocol[i] == 1) {
                for(int g : adj[host[i]]) {
                    adj[i].push_back(g);
                    adj[g].push_back(i);
                }
            }
            if(protocol[i] == 2) {
                for(int g : adj[host[i]]) {
                    adj[i].push_back(g);
                    adj[g].push_back(i);
                }
                tie(x, y) = {i, host[i]};
                adj[x].push_back(y);
                adj[y].push_back(x);
            }
        }
        int best = 0;
        for(int i = 0; i < (1 << n); i++) {
            vector<int> goods;
            for(int j = 0; j < n; j++) {
                if(i & (1 << j)) goods.push_back(j);
            }
            bool ok = true;
            for(int g : goods) {
                for(int h : goods) {
                    if(g == h) continue;
                    for(int k : adj[g]) {
                        if(k == h) ok = false;
                    }
                }
            }
            if(!ok) continue;
            int ans = 0;
            for(int g : goods) {
                ans += confidence[g];
            }
            best = max(best, ans);
            vector<int>().swap(goods);
        }
        return best;
    }
    else if(mip == map && mip == 1) { // Subtask 2
        int ans = 0;
        for(int i = 0; i < n; i++) ans += confidence[i];
        return ans;
    }
    else if(mip == map && mip == 2) { // Subtask 3
        sort(confidence, confidence+n);
        return confidence[n-1];
    }
    else if(mip == map) { // Subtask 4
        // It is a tree
        adj.resize(n);
        int ans[1001][2];
        ans[0][0] = ans[0][1] = 0;
        for(int i = 1; i < n; i++) {
            ans[i][0] = ans[i][1] = 0;
            adj[i].push_back(host[i]);
            adj[host[i]].push_back(i);
        }
        function<int(int, int, int)> dfs = [&](int n, int x, int par) {
            if(ans[n][x]) return ans[n][x];
            if(x == 0) {
                int sum = 0;
                for(int ch : adj[n]) {
                    if(ch == par) continue;
                    sum += dfs(ch, 1, n);
                }
                return ans[n][x] = sum;
            }
            int sum = confidence[n];
            for(int ch : adj[n]) {
                if(ch == par) continue;
                sum += dfs(ch, 0, n);
            }
            return ans[n][x] = max(sum, dfs(n, 0, par));
        };
        return dfs(0, 1, -1);
    }
    else if(map - mip == 1) { // Subtask 5 
        int col[1001];
        col[0] = 0;
        for(int i = 1; i < n; i++) {
            col[i] = (col[host[i]]) ^ (1 ^ (protocol[i]));
        }
        int x = 0;
        for(int i = 0; i < n; i++) {
            if(col[i]) x++;
        }
        return max(x, n-x);
    }
    // Subtask 6
    return -1;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 420 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 0 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Incorrect 21 ms 1428 KB Output isn't correct
13 Halted 0 ms 0 KB -