제출 #586319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586319		SeDunion	친구 (IOI14_friend)	C++17	8 / 100	1 ms	340 KiB

friend

#include "friend.h"
#include<iostream>
 
using namespace std;
 
const int N = 1e6 + 123;
 
int dsu[N];
int val[N];
 
int get(int x) {
	if (x == dsu[x]) return x;
	return dsu[x] = get(dsu[x]);
}
 
int findSample(int n,int confidence[],int host[],int protocol[]){
  for (int i = 1 ; i < n ; ++ i) {
if (host[i] >= i)return -1;}
	for (int i = 0 ; i < n ; ++ i) {
		dsu[i] = i;
		val[i] = confidence[i];
	}
	for (int i = 1 ; i < n ; ++ i) {
		int j = host[i];
		int x = get(i), y = get(j);
		if (x == y) continue;
		dsu[x] = y;
		val[y] = max(val[y], val[x]);
	}
	int ans = 0;
	for (int i = 0 ; i < n ; ++ i) {
		int j = get(i);
		ans += val[j];
		val[j] = 0;
	}
	return ans;
}

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