#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
// Find out best sample
const int maxn = 1010;
typedef long long ll;
vector < int > adj[maxn];
int edges[maxn][maxn];
void add_edge(int v, int u)
{
adj[v].push_back(u);
adj[u].push_back(v);
edges[v][u] = edges[u][v] = 1;
}
vector < int > ord;
int used[maxn];
void bfs(int v)
{
queue < int > q;
used[v] = 1;
q.push(v);
while(!q.empty())
{
int cur = q.front();
q.pop();
ord.push_back(cur);
for (int u : adj[cur])
{
if (used[u] == 0)
{
if (used[cur] == 1)
used[u] = 2;
else
used[u] = 1;
q.push(u);
}
}
}
}
int con[maxn], dp[maxn][2];
void dfs(int v, int p)
{
dp[v][1] = con[v];
used[v] = 1;
for (int u : adj[v])
{
if (u == p)
continue;
dfs(u, v);
dp[v][0] += max(dp[u][0], dp[u][1]);
dp[v][1] += dp[u][0];
}
}
struct edge
{
int v, u, cap;
edge(int _v, int _u, int _cap)
{
v = _v;
u = _u;
cap = _cap;
}
};
struct dinic
{
vector < edge > edges;
vector < int > levels, ptr;
vector < vector < int > > adj;
int n, s, t;
dinic(){};
dinic(int _n, int _s, int _t)
{
n = _n;
s = _s;
t = _t;
ptr.resize(n + 1);
adj.resize(n + 1);
levels.resize(n + 1);
}
void add_edge(int v, int u, int cap)
{
adj[v].push_back(edges.size());
edges.push_back(edge(v, u, cap));
adj[u].push_back(edges.size());
edges.push_back(edge(u, v, 0));
}
bool bfs()
{
for (int i = 0; i <= n; i ++)
levels[i] = -1;
queue < int > q;
q.push(s);
while(!q.empty())
{
int v = q.front();
q.pop();
for (int idx : adj[v])
{
edge cur = edges[idx];
if (cur.cap > 0)
{
if (levels[cur.u] == -1)
{
levels[cur.u] = levels[v] + 1;
q.push(cur.u);
}
}
}
}
return levels[t] != -1;
}
ll get_flow(int v, ll tr)
{
if (v == t)
return tr;
for (; ptr[v] < adj[v].size(); ptr[v] ++)
{
int idx = adj[v][ptr[v]];
edge cur = edges[idx];
if (cur.cap > 0 && levels[cur.u] == levels[v] + 1)
{
ll ps = get_flow(cur.u, min((ll)cur.cap, tr));
if (ps != 0)
{
edges[idx].cap -= ps;
edges[idx ^ 1].cap += ps;
return ps;
}
}
}
return 0;
}
ll maxflow()
{
ll flow = 0;
while(bfs())
{
fill(ptr.begin(), ptr.end(), 0);
ll cur;
while(cur = get_flow(s, 1e9))
{
flow += cur;
}
}
return flow;
}
};
int findSample(int n,int confidence[],int host[],int protocol[])
{
bool only_my = true, only_we = true;
for (int i = 1; i < n; i ++)
{
if (protocol[i] != 1)
only_my = false;
if (protocol[i] != 2)
only_we = false;
}
for (int i = 0; i < n; i ++)
{
con[i] = confidence[i];
}
/**if (n <= 10)
{
for (int i = 1; i < n; i ++)
{
if (protocol[i] == 0)
{
add_edge(i, host[i]);
}
else if (protocol[i] == 1)
{
for (int u : adj[host[i]])
add_edge(u, i);
}
else
{
for (int u : adj[host[i]])
add_edge(u, i);
add_edge(i, host[i]);
}
}
ll ans = 0;
for (int mask = 0; mask < (1 << n); mask ++)
{
bool tf = true;
for (int bit1 = 0; bit1 < n; bit1 ++)
for (int bit2 = 0; bit2 < n; bit2 ++)
{
if ((mask & (1 << bit1)) > 0 && (mask & (1 << bit2)) > 0)
{
if (edges[bit1][bit2])
tf = false;
}
}
///cout << mask << " : " << tf << endl;
if (!tf)
continue;
ll cur = 0;
for (int i = 0; i < n; i ++)
if ((mask & (1 << i)) > 0)
cur += confidence[i];
ans = max(ans, cur);
}
return ans;
}
else if (only_my)
{
int ans = 0;
for (int i = 0; i < n; i ++)
ans += confidence[i];
return ans;
}
else if (only_we)
{
int ans = 0;
for (int i = 0; i < n; i ++)
ans = max(ans, confidence[i]);
return ans;
}
else*/
{
for (int i = 1; i < n; i ++)
{
if (protocol[i] == 0)
{
add_edge(i, host[i]);
}
else
if (protocol[i] == 2)
{
for (int u : adj[host[i]])
add_edge(u, i);
}
}
ll ans = 0;
for (int i = 0; i < n; i ++)
{
if (!used[i])
{
bfs(i);
}
}
int s = n, t = n + 1;
dinic dc(n + 2, n, n + 1);
for (int i = 0; i < n; i ++)
{
if (used[i] == 1)
{
dc.add_edge(s, i, 1);
for (int u : adj[i])
{
dc.add_edge(i, u, 1);
///cout << "edge " << i << " " << u << endl;
}
}
else
{
dc.add_edge(i, t, 1);
}
}
return n - dc.maxflow();
}
}
Compilation message
friend.cpp: In member function 'll dinic::get_flow(int, ll)':
friend.cpp:135:23: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (; ptr[v] < adj[v].size(); ptr[v] ++)
friend.cpp: In member function 'll dinic::maxflow()':
friend.cpp:160:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
160 | while(cur = get_flow(s, 1e9))
| ~~~~^~~~~~~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:260:12: warning: unused variable 'ans' [-Wunused-variable]
260 | ll ans = 0;
| ^~~
friend.cpp:171:10: warning: variable 'only_my' set but not used [-Wunused-but-set-variable]
171 | bool only_my = true, only_we = true;
| ^~~~~~~
friend.cpp:171:26: warning: variable 'only_we' set but not used [-Wunused-but-set-variable]
171 | bool only_my = true, only_we = true;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
344 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
372 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
