#include <queue>
#include <vector>
using namespace std;
#define MAXN 100005
#define pb push_back
#define sz(v) ((int)(v).size())
static int N,*A,*H,*P;
static vector<int> con[MAXN];
static bool visit[MAXN];
void connect(int a,int b){ con[a].pb(b); con[b].pb(a); }
void drawGraph()
{
int i,j;
for (i=1;i<N;i++){
switch (P[i]){
case 0: connect(H[i],i); break;
case 1:
for (j=sz(con[H[i]]);j--;) connect(con[H[i]][j],i);
break;
case 2:
for (j=sz(con[H[i]]);j--;) connect(con[H[i]][j],i);
connect(H[i],i);
break;
}
}
}
int dfs(int n,int val)
{
int i,k,ret=0;
if (n == N) return val;
for (i=sz(con[n]);i--;){
k = con[n][i];
if (visit[k]) break;
}
if (i < 0){
visit[n] = 1;
ret = dfs(n+1,val+A[n]);
}
visit[n] = 0;
int v = dfs(n+1,val);
if (ret < v) ret = v;
return ret;
}
int subtask1()
{
drawGraph();
return dfs(0,0);
}
int subtask2()
{
int ret=0,i;
for (i=0;i<N;i++) ret += A[i];
return ret;
}
int subtask3()
{
int ret=0,i;
for (i=0;i<N;i++) if (ret < A[i]) ret = A[i];
return ret;
}
static int par[MAXN],D[MAXN][2];
void dy(int n)
{
int i,k;
D[n][1] = A[n];
for (i=sz(con[n]);i--;){
k = con[n][i];
if (par[n] == k) continue;
par[k] = n; dy(k);
D[n][0] += D[k][1]; D[n][1] += D[k][0];
}
if (D[n][1] < D[n][0]) D[n][1] = D[n][0];
}
int subtask4()
{
drawGraph(); dy(0);
return D[0][1];
}
static int color[MAXN],match[MAXN],dist[MAXN];
static bool used[MAXN];
void coloring(int n,int c)
{
int i,k;
color[n] = c;
for (i=sz(con[n]);i--;){
k = con[n][i];
if (!color[k]) coloring(k,3-c);
}
}
void bfs()
{
int i;
queue <int> que;
for (i=0;i<N;i++) dist[i] = 1e9;
for (i=0;i<N;i++) if (color[i] == 1 && !used[i]) dist[i] = 0, que.push(i);
while (!que.empty()){
int q = que.front(); que.pop();
for (i=sz(con[q]);i--;){
int k = con[q][i], m = match[k];
if (m >= 0 && dist[m] == 1e9) dist[m] = dist[q]+1, que.push(m);
}
}
}
bool hck(int n)
{
int i;
for (i=sz(con[n]);i--;){
int k = con[n][i], m = match[k];
if (m == -1 || dist[m] == dist[n]+1 && hck(m)){
used[n] = 1; match[k] = n;
return 1;
}
}
return 0;
}
int subtask5()
{
int ret=N,i;
drawGraph();
for (i=0;i<N;i++) if (!color[i]) coloring(i,1);
for (i=0;i<N;i++) match[i] = -1;
for (int flow=1;flow;){
bfs();
flow = 0;
for (i=0;i<N;i++) if (color[i] == 1 && !used[i] && hck(i)) flow++;
ret -= flow;
}
return ret;
}
int findSample(int n,int confidence[],int host[],int protocol[])
{
int i;
N = n; A = confidence; H = host; P = protocol;
if (N <= 10) return subtask1();
for (i=1;i<N;i++) if (protocol[i-1] != protocol[i]) break;
if (i == N){
switch (protocol[0]){
case 0: return subtask4();
case 1: return subtask2();
case 2: return subtask3();
}
}
for (i=1;i<N;i++) if (protocol[i] == 2) break;
if (i == N && N <= 1000){
for (i=0;i<N;i++) if (A[i] != 1) break;
if (i == N) return subtask5();
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
7296 KB |
Output is correct |
2 |
Correct |
0 ms |
7296 KB |
Output is correct |
3 |
Correct |
0 ms |
7296 KB |
Output is correct |
4 |
Correct |
0 ms |
7296 KB |
Output is correct |
5 |
Correct |
0 ms |
7296 KB |
Output is correct |
6 |
Correct |
0 ms |
7296 KB |
Output is correct |
7 |
Correct |
0 ms |
7296 KB |
Output is correct |
8 |
Correct |
0 ms |
7296 KB |
Output is correct |
9 |
Correct |
0 ms |
7296 KB |
Output is correct |
10 |
Correct |
0 ms |
7296 KB |
Output is correct |
11 |
Correct |
0 ms |
7296 KB |
Output is correct |
12 |
Correct |
0 ms |
7296 KB |
Output is correct |
13 |
Correct |
0 ms |
7296 KB |
Output is correct |
14 |
Correct |
0 ms |
7296 KB |
Output is correct |
15 |
Correct |
0 ms |
7296 KB |
Output is correct |
16 |
Correct |
0 ms |
7296 KB |
Output is correct |
17 |
Correct |
0 ms |
7296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
7296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
7296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
7296 KB |
Output is correct |
2 |
Correct |
0 ms |
7296 KB |
Output is correct |
3 |
Correct |
0 ms |
7296 KB |
Output is correct |
4 |
Correct |
0 ms |
7296 KB |
Output is correct |
5 |
Correct |
0 ms |
7296 KB |
Output is correct |
6 |
Correct |
0 ms |
7296 KB |
Output is correct |
7 |
Correct |
0 ms |
7296 KB |
Output is correct |
8 |
Correct |
0 ms |
7296 KB |
Output is correct |
9 |
Correct |
0 ms |
7296 KB |
Output is correct |
10 |
Correct |
0 ms |
7296 KB |
Output is correct |
11 |
Correct |
0 ms |
7296 KB |
Output is correct |
12 |
Correct |
0 ms |
7296 KB |
Output is correct |
13 |
Correct |
0 ms |
7296 KB |
Output is correct |
14 |
Correct |
0 ms |
7296 KB |
Output is correct |
15 |
Correct |
0 ms |
7296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
7296 KB |
Output is correct |
2 |
Correct |
0 ms |
7296 KB |
Output is correct |
3 |
Correct |
0 ms |
7296 KB |
Output is correct |
4 |
Correct |
0 ms |
7296 KB |
Output is correct |
5 |
Correct |
0 ms |
7296 KB |
Output is correct |
6 |
Correct |
0 ms |
7296 KB |
Output is correct |
7 |
Correct |
0 ms |
7296 KB |
Output is correct |
8 |
Correct |
0 ms |
7296 KB |
Output is correct |
9 |
Correct |
0 ms |
7296 KB |
Output is correct |
10 |
Correct |
0 ms |
7296 KB |
Output is correct |
11 |
Correct |
0 ms |
7296 KB |
Output is correct |
12 |
Correct |
0 ms |
7296 KB |
Output is correct |
13 |
Correct |
0 ms |
7296 KB |
Output is correct |
14 |
Correct |
0 ms |
7296 KB |
Output is correct |
15 |
Correct |
0 ms |
7296 KB |
Output is correct |
16 |
Correct |
0 ms |
7296 KB |
Output is correct |
17 |
Correct |
0 ms |
7296 KB |
Output is correct |
18 |
Correct |
0 ms |
7296 KB |
Output is correct |
19 |
Correct |
0 ms |
7296 KB |
Output is correct |
20 |
Correct |
0 ms |
7296 KB |
Output is correct |
21 |
Correct |
0 ms |
7296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
7296 KB |
Output is correct |
2 |
Correct |
0 ms |
7296 KB |
Output is correct |
3 |
Correct |
0 ms |
7296 KB |
Output is correct |
4 |
Correct |
0 ms |
7296 KB |
Output is correct |
5 |
Correct |
0 ms |
7296 KB |
Output is correct |
6 |
Correct |
0 ms |
7296 KB |
Output is correct |
7 |
Correct |
0 ms |
7296 KB |
Output is correct |
8 |
Correct |
0 ms |
7296 KB |
Output is correct |
9 |
Correct |
0 ms |
7296 KB |
Output is correct |
10 |
Correct |
0 ms |
7296 KB |
Output is correct |
11 |
Correct |
0 ms |
7296 KB |
Output is correct |
12 |
Incorrect |
32 ms |
7296 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |