oj.uz

Submission #297213

# Submission time Handle Problem Language Result Execution time Memory
297213 2020-09-11T11:35:19 Z miss_robot Friend (IOI14_friend) C++14
46 / 100
 337 ms 50032 KB 
#include <bits/stdc++.h>
#include "friend.h"

#pragma GCC optimize("O3")

using namespace std;

int st1(int n, int confidence[], int host[], int protocol[]){
	vector<int> g(n);
	for(int i = 1; i < n; i++){
		if(protocol[i]){
			g[i] |= g[host[i]];
			for(int j = 0; j < i; j++) if(g[host[i]]&(1<<j)) g[j] |= (1<<i);
		}
		if(protocol[i] != 1){
			g[i] |= (1<<host[i]);
			g[host[i]] |= (1<<i);
		}
	}
	int t, s = 0;
	for(int i = 0; i < (1<<n); i++){
		t = 0;
		for(int j = 0; j < n; j++) if(i&(1<<j)) t += confidence[j];
		for(int j = 0; j < n; j++) if((i&(1<<j)) && (i&(g[j]))) t = 0;
		s = max(s, t);
	}
	return s;
}

int st2(int n, int confidence[]){
	int s = 0;
	for(int i = 0; i < n; i++) s += confidence[i];
	return s;
}

int st3(int n, int confidence[]){
	int mx = 0;
	for(int i = 0; i < n; i++) mx = max(mx, confidence[i]);
	return mx;
}

void dfs(int u, vector< vector<int> >& g, vector<int>& dp, vector<int>& a){
	for(int v : g[u]){
		dfs(v, g, dp, a);
		a[u] += dp[v];
		dp[u] += a[v];
	}
	dp[u] = max(dp[u], a[u]);
}

int st4(int n, int confidence[], int host[]){
	vector< vector<int> > g(n);
	vector<int> dp(n), a(n);
	for(int i = 1; i < n; i++) g[host[i]].push_back(i);
	for(int i = 0; i < n; i++) dp[i] = confidence[i];
	dfs(0, g, dp, a);
	return dp[0];
}

int bip(int u, vector< vector<int> >& g, vector<int>& vis, int c){
	vis[u] = 1;
	int r = c;
	for(int v : g[u]) if(!vis[v]) r += c^1, bip(v, g, vis, c^1);
	return r;
}

int st5(int n, int host[], int protocol[]){
	vector< vector<int> > g(n);
	for(int i = 1; i < n; i++){
		if(protocol[i]){
			for(int v : g[host[i]]) g[i].push_back(v), g[v].push_back(i);
		}
		else{
			g[i].push_back(host[i]), g[host[i]].push_back(i);
		}
	}
	int s = 0;
	vector<int> vis(n);
	for(int i = 0; i < n; i++) if(!vis[i]){
		vector<int> temp(n);
		s += max(bip(i, g, temp, 0), bip(i, g, vis, 1));
	}
	return s;
}

int findSample(int n, int confidence[], int host[], int protocol[]){
	if(n <= 10) return st1(n, confidence, host, protocol);
	for(int i = 2; i < n; i++) if(protocol[i] != protocol[i-1])
		return st5(n, host, protocol);
	if(protocol[1] == 1) return st2(n, confidence);
	if(protocol[1]) return st3(n, confidence);
	return st4(n, confidence, host);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Incorrect 1 ms 384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 337 ms 50032 KB Memory limit exceeded
13 Halted 0 ms 0 KB -