Submission #1024362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024362		vjudge1	Friend (IOI14_friend)	C++17	46 / 100	18 ms	4188 KiB

friend

#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
namespace BPM{
    vector<int>adj[1010];
    int match[1010],dep[1010],match1[1010],match2[1010],col[1010];
    bitset<1010>vis;
    void AE(int x,int y){
        x++,y++;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int bfs(int n){
        queue<int>q;
        for(int i=1;i<=n;i++) if(col[i]){
            if(!match1[i])
                q.push(i),
                dep[i]=1;
            else dep[i]=0;}
        dep[0]=0;
        while(q.size()){
            int x=q.front();
            q.pop();
            if(dep[x]>=dep[0]&&dep[0])
                continue;
            for(auto i:adj[x])
                if(!dep[match2[i]])
                    dep[match2[i]]=dep[x]+1,
                    q.push(match2[i]);
        }
        return dep[0];
    }
    int dfs(int n){
        if(!n)return 1;
        for(auto i:adj[n]){
            if(dep[match2[i]]==dep[n]+1&&dfs(match2[i]))
                return match2[match1[n]=i]=n,1;
        }
        dep[n]=1e9;
        return 0;
    }
    void dfsc(int i){
        vis[i]=1;
        for(auto n:adj[i]) if(!vis[n])
            col[n]=!col[i],dfsc(n);
        else assert(col[n]^col[i]);
    }
    int runmatch(int n){
        for(int i=1;i<=n;i++)
            if(!vis[i])
                dfsc(i);
        int ans=0;
        while(bfs(n))for(int i=1;i<=n;i++)
            if(!match1[i]&&col[i]) ans+=dfs(i);
        return ans;
    }
}
vector<int>adj[1010];
void AE(int x,int y){
    adj[x].push_back(y);
    adj[y].push_back(x);
}
int bruteforce(int n,int confidence[],int host[],int protocol[]){
    for(int i=1;i<n;i++){
        if(protocol[i])
            for(auto x:adj[host[i]])
                AE(x,i);
        if(protocol[i]%2==0)
            AE(i,host[i]);
    }
    int ans=0;
    for(int msk=1;msk<1<<n;msk++){
        int conf=0;
        for(int i=0;i<n;i++) if(msk&1<<i)
            conf+=confidence[i];
        for(int i=0;i<n;i++) if(msk&1<<i)
            for(auto y:adj[i]) if(msk&1<<y)
                conf=-1; ans=max(ans,conf);
    }
    return ans;
}
int wieht[1010],dp1[1010],dp2[1010];
void dfs(int n){
    dp1[n]=0;
    dp2[n]=wieht[n];
    for(auto x:adj[n]){
        dfs(x);
        dp2[n]+=dp1[x];
        dp1[n]+=max(dp2[x],dp1[x]);
    }
}
int itsatree(int par[],int conf[],int n){
    for(int i=1;i<n;i++)
        adj[par[i]].push_back(i);
    memcpy(wieht,conf,4*n);
    dfs(0);
    return max(dp1[0],dp2[0]);
}
int amatching(int host[],int protoc[],int n){
    for(int i=1;i<n;i++){
        if(protoc[i])
            for(auto x:BPM::adj[host[i]+1])
                BPM::AE(x,i);
        else BPM::AE(i,host[i]);
    }
    return n-BPM::runmatch(n);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
    if(n<=10) return bruteforce(n,confidence,host,protocol);
    set<int>st;
    int ans=0,ans2=0;
    for(int i=0;i<n;i++)
        ans+=confidence[i],ans2=max(ans2,confidence[i]);
    for(int i=1;i<n;i++)
        st.insert(protocol[i]);
    if(st.size()==1)
	    return protocol[1]==1?ans:protocol[1]?ans2:itsatree(host,confidence,n);
    return amatching(host,protocol,n);
}

Compilation message (stderr)

friend.cpp: In function 'int bruteforce(int, int*, int*, int*)':
friend.cpp:77:32: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   77 |             for(auto y:adj[i]) if(msk&1<<y)
      |                                ^~
friend.cpp:78:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |                 conf=-1; ans=max(ans,conf);
      |                          ^~~

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