#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
//#define unx
#ifndef unx
#include "friend.h"
#endif // unx
const int N=1010;
int dd[N],pos[N],x[N],y[N];
vector<int> ad[N];
void add(int i,int j){
ad[i].pb(j);
ad[j].pb(i);
}
void build(int n, int confidence[], int host[], int protocol[]){
forinc(i,1,n){
if(protocol[i-1]!=1)
forv(j,ad[host[i-1]])
add(j,i+1);
if(protocol[i-1]!=2)
add(host[i-1],i+1);
}
}
int dfs(int u){
if(dd[u]) return 0;
dd[u]=1;
forv(v,ad[u]) if(!y[v] || dfs(y[v])){
x[u]=v;
y[v]=u;
return 1;
}
return 0;
}
void dfs(int u,int c){
if(pos[u]) return;
pos[u]=c;
forv(v,ad[u]) dfs(v,c^1);
}
int findSample(int n, int confidence[], int host[], int protocol[]){
int mask=0;
forinc(i,1,n){
host[i-1]++;
protocol[i-1]=1<<protocol[i-1];
mask|=protocol[i-1];
}
if(mask==4){
int tot=0;
forinc(i,1,n) tot=max(tot,confidence[i-1]);
return tot;
}
if(mask==2){
int tot=0;
forinc(i,1,n) tot+=confidence[i-1];
return tot;
}
if(n<=10){
build(n,confidence,host,protocol); n++;
int ret=0;
forinc(i,1,(1<<n)-1){
int suc=1, tot=0;
forinc(j,1,n) if(bit(i,j)){
forv(t,ad[j]) if(bit(i,t)) suc=0;
tot+=confidence[j-1];
}
if(suc) ret=max(ret,tot);
}
return ret;
}
if(n<=1000){
build(n,confidence,host,protocol); n++;
dfs(1,2);
int flow=0;
forinc(i,1,n) if(pos[i]==2){
reset(dd,0);
flow+=dfs(i);
}
return n-flow;
}
}
#ifdef unx
int C[101],H[101],P[101];
main(){
#define task "friend"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
//freopen(task".out","w",stdout);
}
int n=in;
forinc(i,1,n+1) C[i-1]=in;
forinc(i,1,n) H[i-1]=in;
forinc(i,1,n) P[i-1]=in;
cout<<findSample(n,C,H,P);
}
#endif
Compilation message
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
