## 답안 #105991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105991 2019-04-16T04:40:15 Z TuGSGeReL 친구 (IOI14_friend) C++14
69 / 100
58 ms 17408 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], par[2001], fl[2001][2001], st[2001];
vector <int> edg[2001], to[2001];

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();

for (auto x : to[u])
{
if ( !used[x] && fl[u][x] )
{
used[x] = 1;
par[x] = u;
q.push(x);
}
}
}

return used[n] == 1;
}

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, to[host[i]].pub(i), to[i].pub(host[i]);
else
fl[i][host[i]] = 1, to[i].pub(host[i]), to[host[i]].pub(i);
} else {
st[i] = st[host[i]];
for (auto x : edg[host[i]])
{
edg[x].pub(i);
edg[i].pub(x);
if ( st[i] )
fl[x][i] = 1, to[x].pub(i), to[i].push_back(x);
else
fl[i][x] = 1, to[i].pub(x), to[x].pub(i);
}
}
}

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

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;
}```

### 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:209:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = n; par[i] != -1; i = par[i])
^~~
friend.cpp:212:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
ans += mn;
^~~```

#### Subtask #1 11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 512 KB Output is correct

#### Subtask #2 8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 484 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

#### Subtask #3 8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 512 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 3 ms 512 KB Output is correct
8 Correct 3 ms 540 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

#### Subtask #4 19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct

#### Subtask #5 23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 7 ms 3328 KB Output is correct
13 Correct 6 ms 2432 KB Output is correct
14 Correct 20 ms 6528 KB Output is correct
15 Correct 6 ms 2688 KB Output is correct
16 Correct 6 ms 2944 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 4 ms 1920 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 12 ms 5120 KB Output is correct
21 Correct 19 ms 6656 KB Output is correct

#### Subtask #6 0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Runtime error 58 ms 17408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -