## Submission #105973

# Submission time Handle Problem Language Result Execution time Memory
105973 2019-04-16T03:14:44 Z TuGSGeReL Friend (IOI14_friend) C++14
0 / 100
93 ms 6396 KB
```#include "friend.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

int used[2001], pre[3], dp[2001][2], idx, par[2001], fl[2001][2001], st[2001];
vector <int> edg[2001], st1, st0;

int solve1(int n, int confidence[], int host[], int protocol[])
{

int ans = 0;

for (int i = 1; i < n; i++)
{
if ( !protocol[i] )
{
edg[i].pub(host[i]);
edg[host[i]].pub(i);
} else if ( protocol[i] == 1 )
{
for (int j = 0; j < edg[host[i]].size(); j++)
{
edg[edg[host[i]][j]].pub(i);
edg[i].pub(edg[host[i]][j]);
}
} else {

for (int j = 0; j < edg[host[i]].size(); j++)
{
edg[i].pub(edg[host[i]][j]);
edg[edg[host[i]][j]].pub(i);
}

edg[i].pub(host[i]);
edg[host[i]].pub(i);
}
}

for (int i = 0; i < (1 << n); i++)
{
memset(used, 0, sizeof used);
bool boo = 0;
int res = 0;

for (int j = 0; j < n; j++)
{
if ( i & (1 << j) )
{
for ( auto x : edg[j] )
if ( used[x] )
boo = 1;

res += confidence[j];
used[j] = 1;
}
}

if ( !boo )
ans = max(ans, res);
}

return ans;
}

void dfs(int u, int pra)
{
for (auto x : edg[u])
if ( x != pra )
dfs(x, u);

if ( pra != -1 )
{
dp[pra][0] += max(dp[u][1], dp[u][0]);
dp[pra][1] += dp[u][0];
}
}

bool bfs(int u, int n)
{
memset(used, 0, sizeof used);
used[u] = 1;
par[u] = -1;
queue<int>q;
q.push(u);

while (!q.empty())
{
u = q.front();
q.pop();
if ( u == n + 1 )
{
for (auto x : st0)
{
if ( !used[x] && fl[u][x] )
{
q.push(x);
used[x] = 1;
par[x] = u;
}
}
}else if ( u == n )
{
return 1;
} else if ( st[u] ) {
if ( !used[n] && fl[u][n] )
{
par[n] = u;
used[n] = 1;
q.push(n);
}
} else if ( !st[u] )
{
for (auto x : st1)
{
if ( !used[x] && fl[u][x] )
{
par[x] = u;
used[x] = 1;
q.push(x);
}
}
}
}

if ( used[n] )
return 1;

return 0;
}

int findSample(int n,int confidence[],int host[],int protocol[])
{
//	if ( n <= 10 )
//		return solve1(n, confidence, host, protocol);
//
//	for (int i = 1; i < n; i++)
//		pre[protocol[i]]++;
//
//	if ( pre[1] == n - 1 )
//	{
//    	int ans = 0;
//
//		for (int i = 0; i < n; i++)
//    		ans += confidence[i];
//
//		return ans;
//	}
//
//	if ( pre[2] == n - 1 )
//	{
//		int ans = 0;
//
//		for (int i = 0; i < n; i++)
//		ans = max(ans, confidence[i]);
//
//		return ans;
//	}
//
//	if ( pre[0] == n - 1 )
//	{
//		for (int i = 1; i < n; i++)
//		{
//    		edg[host[i]].pub(i);
//    		edg[i].pub(host[i]);
//    	}
//
//    	for (int i = 0; i < n; i++)
//			dp[i][1] = confidence[i];
//
//		dfs(0, -1);
//
//	    return max(dp[0][0], dp[0][1]);
//	}

for (int i = 1; i < n; i++)
{
if ( !protocol[i] )
{
st[i] = 1 ^ st[host[i]];
edg[i].pub(host[i]);
edg[host[i]].pub(i);
if ( st[i] )
fl[host[i]][i] = 1;
else
fl[i][host[i]] = 1;
} else {
for (auto x : edg[host[i]])
{
st[i] = st[x] ^ 1;
edg[x].pub(i);
edg[i].pub(x);
if ( st[i] )
fl[x][i] = 1;
else
fl[i][x] = 1;
}
}
}

for (int i = 0; i < n; i++)
{
if ( st[i] )
fl[i][n] = 1, st1.pub(i);
else
fl[n + 1][i] = 1, st0.pub(i);
}

int ans = 0;

while ( bfs(n + 1, n) )
{
int mn = 1e9;

for (int i = n; par[i] != -1; i = par[i])
mn = min(mn, fl[par[i]][i]);

for (int i = n; par[i] != -1; i = par[i])
fl[par[i]][i] -= mn, fl[i][par[i]] += mn;

ans += mn;
}

return n - ans;
}
/*
10
1 1 1 1 1 1 1 1 1 1
0 0
0 0
1 0
1 1
0 1
4 0
3 0
2 1
5 0
*/
/*
5
1 1 1 1 1
0 1
1 1
2 0
1 0
*/```

### Compilation message

```friend.cpp: In function 'int solve1(int, int*, int*, int*)':
friend.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < edg[host[i]].size(); j++)
~~^~~~~~~~~~~~~~~~~~~~~
friend.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < edg[host[i]].size(); j++)
~~^~~~~~~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:235:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = n; par[i] != -1; i = par[i])
^~~
friend.cpp:238:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
ans += mn;
^~~```

#### Subtask #1 0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #3 0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #4 0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #5 0 / 23.0

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

#### Subtask #6 0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -