oj.uz

Submission #961941

# Submission time Handle Problem Language Result Execution time Memory
961941 2024-04-12T19:11:12 Z IUA_Hasin Friend (IOI14_friend) C++17
27 / 100
 20 ms 2648 KB 
#include "friend.h"
#include <bits/stdc++.h>
 
#define endl                                "\n"
#define yeap                                cout<<"YES"<<endl
#define nope                                cout<<"NO"<<endl
#define ll                                  long long
 
using namespace std;

const ll M = 1e5;

vector<vector<ll>> subsets;
vector<ll> subset;
ll arr[M];

const ll N = 1e4;
vector<ll> v[N];
ll deg[N];
ll vis[N];

void subs(ll i, ll n){
    if(i==n){
        subsets.push_back(subset);
        return;
    } else {
        subs(i+1, n);
        subset.push_back(i+1);
        subs(i+1, n);
        subset.pop_back();
        return;
    }
}

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
	if(n<=10){
		subs(-1, n-1);
		ll status = 1;

		// for(ll i=0; i<subsets.size(); i++){
		// 	for(ll j=0; j<subsets[i].size(); j++){
		// 		cout << subsets[i][j] << " ";
		// 	}
		// 	cout<<endl;
		// }

		for(int i=1; i<n; i++){
			ll a = host[i];
			ll b = protocol[i];
			if(b==0){
				v[i].push_back(a);
				v[a].push_back(i);
			} else if(b==1){
				for(int j=0; j<v[a].size(); j++){
					ll c = v[a][j];
					v[i].push_back(c);
					v[c].push_back(i);
				}
			} else {
				for(int j=0; j<v[a].size(); j++){
					ll c = v[a][j];
					v[i].push_back(c);
					v[c].push_back(i);
				}
				v[i].push_back(a);
				v[a].push_back(i);
			}
		}

		ll stat[n+1][n+1];
		for(int i=0; i<n+1; i++){
			for(int j=0; j<n+1; j++){
				stat[i][j] = 0;
			}
		}


		for(int i=0; i<n; i++){
			for(int j=0; j<v[i].size(); j++){
				ll a = v[i][j];
				stat[i][a] = 1;
			}
		}

		// for(int i=0; i<n+1; i++){
		// 	for(int j=0; j<n+1; j++){
		// 		cout << stat[i][j] << " ";
		// 	}
		// 	cout<<endl;
		// }

		ll ans = 0;

		for(int i=0; i<subsets.size(); i++){
			status = 1;
			ll a = subsets[i].size();
			for(int j=0; j<a; j++){
				for(int k=j+1; k<a; k++){
					ll b = subsets[i][j];
					ll c = subsets[i][k];
					if(stat[b][c]==1){
						status = -1;
					}
				}
			}
			// cout << status << endl;
			if(status==1){
				ll temp = 0;
				for(int j=0; j<a; j++){
					ll b = subsets[i][j];
					ll c = confidence[b];
					temp = temp+c;
				}
				ans = max(temp, ans);
			}
		}

		return ans;




	} else if(protocol[1]==1){
		ll ans = 0;
		for(int i=0; i<n; i++){
			ans = ans+confidence[i];
		}
		return ans;
	} else if(protocol[1]==2){
		int ans = -1;
		for(int i=0; i<n; i++){
			ans = max(ans, confidence[i]);
		}
		return ans;
	}
}

Compilation message

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0; j<v[a].size(); j++){
      |                  ~^~~~~~~~~~~~
friend.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int j=0; j<v[a].size(); j++){
      |                  ~^~~~~~~~~~~~
friend.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int j=0; j<v[i].size(); j++){
      |                 ~^~~~~~~~~~~~
friend.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i=0; i<subsets.size(); i++){
      |                ~^~~~~~~~~~~~~~~
friend.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 31.0

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