oj.uz

답안 #780317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780317 2023-07-12T08:13:58 Z fatemetmhr 친구 (IOI14_friend) C++17
69 / 100
 527 ms 62572 KB 
//  ~ Be Name Khoda ~  //

#include "friend.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int cmp[maxn5], hs[maxn5], ty[maxn5];
ll val[maxn5];
int n, dp[maxn5][2], mat[maxn5];
vector <int> adj[maxn5];
bool mark[maxn5];

int sub1(){
	for(int i = 1; i < n; i++){
		if(ty[i] == 0){
			adj[i].pb(hs[i]);
			adj[hs[i]].pb(i);
		}
		else if(ty[i] == 1){
			for(auto u : adj[hs[i]]){
				adj[i].pb(u);
				adj[u].pb(i);
			}
		}
		else{
			for(auto u : adj[hs[i]]){
				adj[i].pb(u);
				adj[u].pb(i);
			}
			adj[hs[i]].pb(i);
			adj[i].pb(hs[i]);
		}
	}

	int ans = 0;
	for(int mask = 1; mask < (1 << n); mask++){
		bool re = true;
		for(int i = 0; i < n; i++) if((mask >> i)&1)
			for(auto u : adj[i]) if((mask >> u)&1)
				re = false;
		if(re){
			int sum = 0;
			for(int i = 0; i < n; i++) if((mask >> i)&1)
				sum += val[i];
			ans = max(ans, sum);
		}
	}
	return ans;
}	

int sub2(){
	ll sum = 0;
	for(int i = 0; i < n; i++)
		sum += val[i];
	return sum;
}

int sub3(){
	ll mx = 0;
	for(int i = 0; i < n; i++)
		mx = max(mx, val[i]);
	return mx;
}

void dfs4(int v){
	dp[v][1] = val[v];
	for(auto u : adj[v]){
		dfs4(u);
		dp[v][0] += max(dp[u][0], dp[u][1]);
		dp[v][1] += dp[u][0];
	}
}	

int sub4(){
	for(int i = 1; i < n; i++)
		adj[hs[i]].pb(i);
	dfs4(0);
	return max(dp[0][0], dp[0][1]);
}

bool dfs5(int v){
	mark[v] = true;
	for(auto u : adj[v]) if(mat[u] == -1 || (!mark[mat[u]] && dfs5(mat[u]))){
		mat[v] = u;
		mat[u] = v;
		return true;
	}
	return false;
}

int sub5(){
	for(int i = 1; i < n; i++){
		cmp[i] = cmp[hs[i]] ^ ty[i] ^ 1;
		if(ty[i] == 0){
			adj[i].pb(hs[i]);
			adj[hs[i]].pb(i);
		}
		else{
			for(auto u : adj[hs[i]]){
				adj[i].pb(u);
				adj[u].pb(i);
			}
		}
	}
	bool con = true;
	memset(mat, -1, sizeof mat);
	int ans = 0;
	while(con){
		con = false;
		memset(mark, false, sizeof mark);
		for(int i = 0; i < n; i++) if(!mark[i] && cmp[i] && mat[i] == -1 && dfs5(i)){
			con = true;
			ans++;
		}
	}
	return n - ans;
}	

// Find out best sample
int findSample(int n,int confidence[], int host[], int protocol[]){
	::n = n;
	for(int i = 1; i < n; i++){
		val[i] = confidence[i];
		hs[i] = host[i];
		ty[i] = protocol[i];
	}
	val[0] = confidence[0];
	if(n <= 10)
		return sub1();
	bool ok = true;
	for(int i = 1; i < n; i++)
		ok &= (protocol[i] == protocol[1]);
	if(ok){
		if(protocol[1] == 0)
			return sub4();
		if(protocol[1] == 1)
			return sub2();
		return sub3();
	}
	return sub5();
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12056 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 6 ms 12068 KB Output is correct
7 Correct 5 ms 12060 KB Output is correct
8 Correct 6 ms 12052 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 6 ms 11988 KB Output is correct
15 Correct 6 ms 12056 KB Output is correct
16 Correct 8 ms 12056 KB Output is correct
17 Correct 8 ms 12056 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 7 ms 12012 KB Output is correct
4 Correct 7 ms 12240 KB Output is correct
5 Correct 6 ms 12060 KB Output is correct
6 Correct 7 ms 12056 KB Output is correct
7 Correct 6 ms 12056 KB Output is correct
8 Correct 6 ms 12008 KB Output is correct
9 Correct 6 ms 12020 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12020 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 6 ms 12036 KB Output is correct
8 Correct 9 ms 12112 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 6 ms 12060 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 6 ms 12044 KB Output is correct
14 Correct 6 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 12096 KB Output is correct
6 Correct 6 ms 12076 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 12072 KB Output is correct
9 Correct 6 ms 12172 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 7 ms 14548 KB Output is correct
12 Correct 8 ms 14508 KB Output is correct
13 Correct 7 ms 14548 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 9 ms 14548 KB Output is correct
16 Correct 10 ms 14548 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 7 ms 14548 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 7 ms 14548 KB Output is correct
21 Correct 7 ms 14520 KB Output is correct

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12052 KB Output is correct
3 Correct 6 ms 12052 KB Output is correct
4 Correct 8 ms 11988 KB Output is correct
5 Correct 6 ms 12068 KB Output is correct
6 Correct 6 ms 12060 KB Output is correct
7 Correct 6 ms 12060 KB Output is correct
8 Correct 7 ms 12084 KB Output is correct
9 Correct 6 ms 11988 KB Output is correct
10 Correct 6 ms 12052 KB Output is correct
11 Correct 7 ms 11988 KB Output is correct
12 Runtime error 527 ms 62572 KB Memory limit exceeded
13 Halted 0 ms 0 KB -