oj.uz

Submission #48997

# Submission time Handle Problem Language Result Execution time Memory
48997 2018-05-21T06:26:54 Z Namnamseo Friend (IOI14_friend) C++17
35 / 100
 3 ms 1592 KB 
#include "friend.h"

// Find out best sample

int sum[100001][2];

int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }

bool edge[11][11];

int naive(int n,int cf[],int hst[],int pt[]){
	for(int i=1; i<n; ++i){
		int h=hst[i];
		if(pt[i] == 0){
			edge[h][i]=edge[i][h]=true;
		} else {
			for(int j=0; j<n; ++j) if(edge[h][j]) edge[j][i]=edge[i][j]=true;
			if(pt[i] == 2){
				edge[h][i]=edge[i][h]=true;
			}
		}
	}
	int msk=(1<<n);
	int ans=0;
	for(int i=0; i<msk; ++i){
		int s[11], t=0;
		int cur=0;
		for(int j=0; j<n; ++j) if(1&(i>>j)) s[t++]=j, cur+=cf[j];
		bool wa=0;
		for(int a=0; a<t; ++a){
			for(int b=a+1; b<t; ++b){
				if(edge[s[a]][s[b]]){
					wa=1; break;
				}
			}
			if(wa) break;
		}
		if(!wa) ans=max(ans, cur);
	}
	return ans;
}
#include <cstdio>
int findSample(int n,int confidence[],int host[],int protocol[]){
	if(n <= 10){
//		return naive(n,confidence,host, protocol);
	}
	for(int i=0; i<n; ++i) sum[i][1]=confidence[i], sum[i][0]=0;
	int allprot=0;
	for(int i=n-1; 0<i; --i){
		int h=host[i];
		int p=protocol[i];
		if(p==2) ++allprot;
		if(p == 0){
			sum[h][0] += max(sum[i][0], sum[i][1]);
			sum[h][1] += sum[i][0];
		} else if(p == 1){
			sum[h][0] += sum[i][0];
			sum[h][1] += max(sum[i][0], sum[i][1]);
		} else if(p == 2){
			sum[h][1] += max(0, -confidence[h] + max(sum[i][0], sum[i][1]));
			sum[h][0] += sum[i][0];
		}
		//printf("Host(%d)| %d %d\n", h, sum[h][1], sum[h][0]);
	}
	if(allprot == n-1){
		int ans=0;
		for(int i=0; i<n; ++i) ans=max(ans, confidence[i]);
		return ans;
	}
	return max(sum[0][0], sum[0][1]);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 536 KB Output is correct
3 Correct 2 ms 776 KB Output is correct
4 Correct 2 ms 840 KB Output is correct
5 Correct 2 ms 840 KB Output is correct
6 Correct 2 ms 840 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Incorrect 2 ms 872 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 872 KB Output is correct
2 Correct 2 ms 900 KB Output is correct
3 Correct 2 ms 904 KB Output is correct
4 Correct 2 ms 912 KB Output is correct
5 Correct 2 ms 940 KB Output is correct
6 Correct 2 ms 968 KB Output is correct
7 Correct 2 ms 992 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 2 ms 1116 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1240 KB Output is correct
2 Correct 3 ms 1240 KB Output is correct
3 Correct 2 ms 1240 KB Output is correct
4 Correct 3 ms 1240 KB Output is correct
5 Correct 2 ms 1284 KB Output is correct
6 Correct 2 ms 1292 KB Output is correct
7 Correct 2 ms 1292 KB Output is correct
8 Correct 3 ms 1312 KB Output is correct
9 Correct 2 ms 1312 KB Output is correct
10 Correct 3 ms 1328 KB Output is correct
11 Correct 3 ms 1332 KB Output is correct
12 Correct 3 ms 1332 KB Output is correct
13 Correct 3 ms 1352 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct

Subtask #5
0 / 23.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1440 KB Output is correct
2 Correct 2 ms 1444 KB Output is correct
3 Correct 2 ms 1448 KB Output is correct
4 Correct 3 ms 1456 KB Output is correct
5 Correct 3 ms 1456 KB Output is correct
6 Correct 2 ms 1460 KB Output is correct
7 Incorrect 3 ms 1592 KB Output isn't correct
8 Halted 0 ms 0 KB -