제출 #1276159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276159		KindaGoodGames	친구 (IOI14_friend)	C++17	11 / 100	1096 ms	131072 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>

using namespace std;

struct UnionFind{
	vector<int> par;

	UnionFind(int n){
		par.resize(n);
		iota(par.begin(),par.end(),0);
	}

	int find(int i){
		if(par[i] == i) return i;
		return par[i] = find(par[i]);
	}

	void unite(int i, int j){
		i = find(i);
		j = find(j);
		par[i] = j;
	}
};

vector<int> arr,dpT, dpN;
	vector<vector<int>> adj;

void DFS(int v){
	dpT[v] = arr[v];
	int oth1 = 0;

	for(auto u : adj[v]){
		DFS(u);
		dpT[v] += dpN[u];
		dpN[v] += dpT[u];
	}
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	int ans=0;
    vector<vector<bool>> adj(n, vector<bool>(n));
	for(int i = 1; i < n; i++){
        if(protocol[i] == 0){ 
		    adj[host[i]][i] = true;
		    adj[i][host[i]] = true;
        }else if(protocol[i] == 1){
            for(int u = 0; u < n; u++){
                if(adj[host[i]][u]){
                    adj[u][i] = true; 
                    adj[i][u] = true;  
                }
            }
        }else{
		    adj[host[i]][i] = true;
		    adj[i][host[i]] = true;
            for(int u = 0; u < n; u++){
                if(adj[host[i]][u]){
                    adj[u][i] = true; 
                    adj[i][u] = true;  
                }
            }
        }
	}
	
    int p2 = 1 << n;

    for(int m = 0; m < p2; m++){
        int val = 0;
        for(int i = 0; i < n; i++){
            if(m & (1 << i)){
                val += confidence[i];
            }
        }

        bool valid = true;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){ 
                int a = (m & (1 << i));
                int b = (m & (1 << j));
                if(a && b){
                    if(adj[i][j]){
                        valid = false;
                        break;
                    }
                }
            }
            if(!valid) break;
        }
        if(valid){
            ans = max(ans, val);
        }
    }
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31