oj.uz

Submission #810290

# Submission time Handle Problem Language Result Execution time Memory
810290 2023-08-06T08:03:05 Z Kerim Friend (IOI14_friend) C++17
69 / 100
 21 ms 4436 KB 
#include "friend.h"
#include "bits/stdc++.h"
#define pb(x) push_back(x)
using namespace std;
const int N = 1005;
vector<int> adj[N];

void add_edge(int u, int v){
	adj[u].pb(v);
	adj[v].pb(u);
}

int dp[N][2];
void dfs(int nd, int pr, int val[]){
	dp[nd][1] = val[nd];
	dp[nd][0] = 0;
	for (auto c: adj[nd]){
		if (c == pr)
			continue;
		dfs(c, nd, val);
		dp[nd][1] += dp[c][0];
		dp[nd][0] += max(dp[c][0], dp[c][1]);
	}
}

int vis[N], col[N], matched[N];
void dfs0(int nd, vector<int>&L, vector<int> &R){
	vis[nd] = 1;
	if (!col[nd]) L.pb(nd);
	else R.pb(nd);
	for (auto to: adj[nd])
		if (!vis[to]){
			col[to] = col[nd] ^ 1;
			dfs0(to, L, R);
		}
}

bool dfs1(int nd){
	if (vis[nd])
		return 0;
	vis[nd] = 1;
	for (auto x: adj[nd]){
		if (matched[x] == -1 or dfs1(matched[x])){
			matched[x] = nd;
			return 1;
		}
	}
	return 0;
}
const int MAXN = 1e5+5;
int p[MAXN], q[MAXN];
int findSample(int n,int arr[],int host[],int protocol[]){
	for (int i = 0; i < n; i++)
		adj[i].clear();
	bool subtask1 = (n <= 10);
	bool subtask2 = true, subtask3 = true;
	bool subtask4 = true, subtask5 = true;
	// Build graph
	for (int i = 1; i < n; i++){
		int v = host[i], p = protocol[i];
		subtask4 &= (p == 0);
		subtask2 &= (p == 1);
		subtask3 &= (p == 2);
		subtask5 &= (p <= 1);
	}
	if (n <= 1000){
		for (int i = 1; i < n; i++){
			int v = host[i], p = protocol[i];
			if (p == 0)//IAmYourFriend
				add_edge(v, i);
			else if(p == 1){//MyFriendsAreYourFriends
				for (auto to: adj[v])
					add_edge(to, i);
			}
			else{//WeAreYourFriends
				for (auto to: adj[v])
					add_edge(to, i);
				add_edge(v, i);
			}
		}
	}
	int answer = 0;
	if (subtask1){
		for (int mask = 0; mask < (1<<n); mask++){
			bool bad = 0;
			int sum = 0;
			for (int i = 0; i < n; i++)
				if (mask>>i&1){
					sum += arr[i];
					for (auto to: adj[i])
						bad |= (mask>>to&1);
				}
			if (!bad)
				answer = max(answer, sum);
		}
	}
	else if(subtask2){
		for (int i = 0; i < n; i++)
			answer += arr[i];
	}
	else if (subtask3){
		for (int i = 0; i < n; i++)
			answer = max(answer, arr[i]);
	}
	else if (subtask4){
		dfs(0, -1, arr);
		answer = max(dp[0][0], dp[0][1]);
	}
	else if(subtask5){
		for (int i = 0; i < n; i++)
			vis[i] = col[i] = 0;
		int MM = 0;
		for (int i = 0; i < n; i++)
			if (!vis[i]){
				vector<int> L, R;
				dfs0(i, L, R);
				// Kuhn's algorithm
				for (auto x: R)
					matched[x] = -1;
				for (auto x: L){
					for (auto y: L)
						vis[y] = false;
					dfs1(x);
				}
				for (auto x: R)
					MM += (matched[x] != -1);
			}
		answer = n - MM; 
	}
	else{
		// puts("subtask6");
		for (int i = 0; i < n; i++)
			p[i] = arr[i], q[i] = 0;
		for (int i = n-1; i > 0; i--){
			int pp = protocol[i];
			int v = host[i];
			if (pp == 2){ //WeAreYourFriends
				p[v] = max(p[v] + q[i], p[i] + q[v]);
				q[v] = q[v] + q[i];
			}
			else if (pp == 1){//MyFriendsAreYourFriends
				p[v] = max(p[v]+p[i], max(p[v] + q[i], p[i] + q[v]));
				q[v] = q[v] + q[i];
			}
			else{//IamYourFriend
				p[v] = p[v] + q[i];
				q[v] = max(p[i] + q[v], q[v] + q[i]);
			}
			// cout<<i<<"->"<<v<<": "<<p[v]<<" "<<q[v]<<endl;
		}
		answer = max(p[0], q[0]);
	}
	return answer;
}

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:60:7: warning: unused variable 'v' [-Wunused-variable]
   60 |   int v = host[i], p = protocol[i];
      |       ^

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 4 ms 4184 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 4 ms 4052 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 4 ms 4436 KB Output is correct

Subtask #4
19.0 / 19.0

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

Subtask #5
23.0 / 23.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Runtime error 21 ms 3940 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -