#include "friend.h"
#include <vector>
#include <algorithm>
#include <random>
const int MAXN = 1000;
namespace Solver {
std::vector<int> adj[MAXN];
void push_edge( int a, int b ) {
adj[a].push_back( b );
adj[b].push_back( a );
}
void make_graph( int n, int host[], int protocol[] ) {
for( int i = 1 ; i < n ; i++ ){
if( protocol[i] == 0 )
push_edge( i, host[i] );
else if( protocol[i] == 1 ){
for( int x : adj[host[i]] )
push_edge( x, i );
}else{
for( int x : adj[host[i]] )
push_edge( x, i );
push_edge( host[i], i );
}
}
}
int brute_force( int n, int v[] ) {
int ret = 0;
for( int mask = (1 << n) ; mask-- ; ){
int sum = 0;
int isin[10];
for( int i = 0 ; i < n ; i++ ){
isin[i] = !!(mask & (1 << i));
sum += isin[i] * v[i];
}
bool bad = false;
for( int i = 0 ; i < n ; i++ )
for( int j : adj[i] )
bad |= (isin[i] & isin[j]);
if( !bad )
ret = sum > ret ? sum : ret;
}
return ret;
}
const int NIL = -1;
int pair[MAXN];
bool viz[MAXN];
bool try_pair( int u ) {
viz[u] = true;
for( int v : adj[u] )
if( pair[v] == NIL ){
pair[v] = u;
pair[u] = v;
return true;
}
viz[u] = true;
for( int v : adj[u] )
if( !viz[v] ){
viz[v] = true;
if( try_pair( pair[v] ) ){
pair[v] = u;
pair[u] = v;
return true;
}
}
return false;
}
int bipartite( int n ) { // no need for v
std::mt19937 rng( 6969 );
for( int i = 0 ; i < n ; i++ ){
pair[i] = NIL;
std::shuffle( adj[i].begin(), adj[i].end(), rng );
}
bool added = true;
while( added ){
added = false;
for( int i = 0 ; i < n ; i++ )
viz[i] = false;
for( int i = 0 ; i < n ; i++ )
if( !viz[i] && pair[i] == NIL )
added |= try_pair( i );
}
int ans = 0;
for( int i = 0 ; i < n ; i++ )
ans += (pair[i] != NIL);
return n - (ans >> 1);
}
};
// Find out best sample
int findSample( int n, int confidence[], int host[], int protocol[] ) {
if( n > 1000 )
return -1;
Solver::make_graph( n, host, protocol );
if( n <= 10 )
return Solver::brute_force( n, confidence );
int freq[3] = { 0, 0, 0 };
int not1 = 0;
for( int i = 0 ; i < n ; i++ ){
if( confidence[i] != 1 )
not1++;
if( i > 0 )
freq[protocol[i]]++;
}
if( freq[1] == n - 1 ){
int ret = 0;
for( int i = 0 ; i < n ; i++ )
ret += confidence[i];
return ret;
}
if( freq[2] == n - 1 ){
int ret = 0;
for( int i = 0 ; i < n ; i++ )
ret = confidence[i] > ret ? confidence[i] : ret;
return ret;
}
if( !not1 && freq[2] == 0 )
return Solver::bipartite( n );
}
Compilation message
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
156 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
360 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
460 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1372 KB |
Output is correct |
2 |
Correct |
6 ms |
4188 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
3 ms |
3164 KB |
Output is correct |
5 |
Correct |
5 ms |
4296 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
860 KB |
Output is correct |
8 |
Correct |
1 ms |
1116 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
5 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
19 ms |
1628 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |