Submission #239883

#	Time	Username	Problem	Language	Result	Execution time	Memory
239883		LittleFlowers__	Friend (IOI14_friend)	C++17	69 / 100	37 ms	2936 KiB

friend

#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)
            forv(j,ad[host[i]])
                add(j,i+1);
        if(protocol[i]!=2)
            add(host[i],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 confi[1010];

ii dfs1(int u,int p=-1){
    dd[u]=1;
    int f=0, g=confi[u];
    forv(v,ad[u]) if(v!=p){
        int x,y; tie(x,y)=dfs1(v,u);
        f+=max(x,y);
        g+=x;
    }
    return {f,g};
};

int findSample(int n, int confidence[], int host[], int protocol[]){
    int mask=0;
    forinc(i,1,n-1){
        host[i]++;
        protocol[i]=1<<protocol[i];
        mask|=protocol[i];
    }
    forinc(i,1,n) confi[i]=confidence[i-1];
    if(mask==1){
        build(n,confidence,host,protocol);
        int tot=0;
        forinc(i,1,n) if(!dd[i]){
            int x,y; tie(x,y)=dfs1(i);
            tot+=max(x,y);
        }
        return tot;
    }
    if(mask==2){
        int tot=0;
        forinc(i,1,n) tot+=confidence[i-1];
        return tot;
    }
    if(mask==4){
        int tot=0;
        forinc(i,1,n) tot=max(tot,confidence[i-1]);
        return tot;
    }
    if(n<=10){
        build(n,confidence,host,protocol);
        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);
        forinc(i,1,n) if(!pos[i]) dfs(i,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[1010],H[1010],P[1010];
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) C[i-1]=in;
    forinc(i,1,n-1) H[i]=in, P[i]=in;
    cout<<findSample(n,C,H,P);
}
#endif

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:129:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31