oj.uz

Submission #404191

# Submission time Handle Problem Language Result Execution time Memory
404191 2021-05-13T23:35:11 Z peuch Friend (IOI14_friend) C++17
69 / 100
 32 ms 2884 KB 
#include "friend.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;

int dp[MAXN][2];
int v[MAXN];
int cor[MAXN];

int marcB[MAXN];
int match[MAXN];

int marc[MAXN];

vector<int> ar[MAXN];
vector<int> grp[2];

int mask[MAXN];

bool dfs(int cur);
void calc(int cur);

int sub1(int n, int confidence[], int host[], int protocol[]){
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	
	for(int i = 1; i < n; i++){
		if(protocol[i] != 1){
			mask[i] |= (1 << host[i]);
			mask[host[i]] |= (1 << i);
		}
		if(protocol[i] != 0){
			for(int j = 0; j < n; j++){
				if((1 << j) & mask[host[i]]) 
					mask[i] |= (1 << j), mask[j] |= (1 << i);
			}
		}
		if(mask[i] & (1 << i)) mask[i] ^= (1 << i);
	}
	if(mask[0] & 1) mask[0] ^= 1;
	
	int ans = 0;
	for(int i = 0; i < (1 << n); i++){
		int auxMask = 0;
		int sum = 0;
		for(int j = 0; j < n; j++)
			if((1 << j) & i) auxMask |= mask[j], sum += v[j];
		if(auxMask & i) continue;
		ans = max(ans, sum);
	}
	return ans;
}

int sub2(int n, int confidence[], int host[], int protocol[]){
	int sum = 0;
	for(int i = 0; i < n; i++)
		sum += confidence[i];
	return sum;
}

int sub3(int n, int confidence[], int host[], int protocol[]){
	int maxi = 0;
	for(int i = 0; i < n; i++)
		maxi = max(confidence[i], maxi);
	return maxi;
}

int sub4(int n, int confidence[], int host[], int protocol[]){
	
	memset(dp, -1, sizeof(dp));
	
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	for(int i = 1; i < n; i++)
		ar[host[i]].push_back(i);
 	calc(0);
	return dp[0][1];
}

int sub5(int n, int confidence[], int host[], int protocol[]){
	
	for(int i = 0; i < n; i++)
		v[i] = confidence[i];
	
	grp[0].push_back(0);
	cor[0] = 0;
	for(int i = 1; i < n; i++){
		if(protocol[i] == 0){
			ar[host[i]].push_back(i);
			ar[i].push_back(host[i]);
			cor[i] = !cor[host[i]];
			grp[cor[i]].push_back(i);
		}
		else{
			for(int j = 0; j < ar[host[i]].size(); j++){
				ar[ar[host[i]][j]].push_back(i);
				ar[i].push_back(ar[host[i]][j]);
			}
			cor[i] = cor[host[i]];
			grp[cor[i]].push_back(i);
		}
	}
	
	for(int i = 0; i < n; i++)
		match[i] = -1;
	
	bool flag = true;
	int ans = 0;
	while(flag){
		flag = false;
		for(int i = 0; i < n; i++) marcB[i] = 0;
		for(int i = 0; i < grp[0].size(); i++){
			int cur = grp[0][i];
			if(match[cur] != -1) continue;
			if(dfs(cur)){
				flag = true;
				ans++;
			}		
		}
	}
	ans = n - ans;
	return ans;
}

int findSample(int n,int confidence[],int host[],int protocol[]){
	
	bool caso1 = true;
	bool caso2 = true;
	bool caso3 = true;
	bool caso4 = true;
	bool caso5 = true;
	if(n > 10) caso1 = false;
	for(int i = 1; i < n; i++){
		caso2 &= protocol[i] == 1;
		caso3 &= protocol[i] == 2;
		caso4 &= protocol[i] == 0;
		caso5 &= protocol[i] != 2;
	}
	
	if(caso1) return sub1(n, confidence, host, protocol);
	if(caso2) return sub2(n, confidence, host, protocol); 
	if(caso3) return sub3(n, confidence, host, protocol);
	if(caso4) return sub4(n, confidence, host, protocol);
	if(caso5) return sub5(n, confidence, host, protocol);
}

bool dfs(int cur){
	for(int i = 0; i < ar[cur].size(); i++)	{
		int viz = ar[cur][i];
		if(marcB[viz]) continue;
		marcB[viz] = 1;
		if(match[viz] == -1 || dfs(match[viz])){
			match[cur] = viz;
			match[viz] = cur;
			return true;
		}
	}
	return false;
}

void calc(int cur){
	dp[cur][0] = 0;
	dp[cur][1] = v[cur];
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		calc(viz);
		dp[cur][0] += dp[viz][1];
		dp[cur][1] += dp[viz][0];
	}
	dp[cur][1] = max(dp[cur][1], dp[cur][0]);
}

Compilation message

friend.cpp: In function 'int sub5(int, int*, int*, int*)':
friend.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int j = 0; j < ar[host[i]].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
friend.cpp:113:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0; i < grp[0].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
friend.cpp: In function 'bool dfs(int)':
friend.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for(int i = 0; i < ar[cur].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
friend.cpp: In function 'void calc(int)':
friend.cpp:165:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:146:1: warning: control reaches end of non-void function [-Wreturn-type]
  146 | }
      | ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 220 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Runtime error 32 ms 2884 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -