Submission #1102986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102986		alexander707070	Friend (IOI14_friend)	C++14	27 / 100	20 ms	3048 KiB

friend

#include<bits/stdc++.h>
#include "friend.h"

#define MAXN 1007
using namespace std;

struct edge{
    int to;
    bool cap;
    int rev;
};

int n;
vector<int> v[MAXN];
vector<edge> g[MAXN];

long long ans,cost[MAXN];
int mins,maxs,where[MAXN];

bool li[MAXN];

void brute(int x,long long res){
    if(x==0){
        ans=max(ans,res);
        return;
    }

    brute(x-1,res);

    int br=0;
    for(int i:v[x]){
        if(li[i])br++;
    }

    if(br==0){
        li[x]=true;
        brute(x-1,res+cost[x]);
        li[x]=false;
    }
}

long long dp[MAXN][2];
bool vis[MAXN][2];

long long ff(int x,int p,int parent){
    if(vis[x][p])return dp[x][p];
    vis[x][p]=true;

    if(p==0){
        dp[x][p]=cost[x];
        for(int i:v[x]){
            if(i==parent)continue;
            dp[x][p]+=ff(i,1,x);
        }
    }

    long long sum=0;
    for(int i:v[x]){
        if(i==parent)continue;
        sum+=ff(i,0,x);
    }

    dp[x][p]=max(dp[x][p],sum);
    return dp[x][p];
}

void add_edge(int from,int to){
    g[from].push_back({to,1,int(g[to].size())});
    g[to].push_back({from,0,int(g[from].size())-1});
}

int source,sink,flow,maxflow,mvc;

void dfs(int x,int side){
    li[x]=true;
    where[x]=side;

    if(side==0)add_edge(source,x);
    if(side==1)add_edge(x,sink);

    for(int i:v[x]){
        if(side==0)add_edge(x,i);

        if(li[i])continue;
        dfs(i,side^1);
    }
}

int u[MAXN],tim;

int fordfulk(int x){
    if(x==sink)return 1;

    u[x]=tim;
    for(int i=0;i<g[x].size();i++){
        if(u[g[x][i].to]==tim or !g[x][i].cap)continue;

        int curr=fordfulk(g[x][i].to);
        if(curr>0){
            g[x][i].cap=false;
            g[g[x][i].to][g[x][i].rev].cap=true;
            return 1;
        }
    }

    return 0;
}

void dfs2(int x){
    u[x]=tim;

    for(int i=0;i<g[x].size();i++){
        if(u[g[x][i].to]==tim or !g[x][i].cap)continue;

        dfs2(g[x][i].to);
    }
}

int findSample(int N,int confidence[],int host[],int protocol[]){
//int findSample(int N,vector<int> confidence,vector<int> host,vector<int> protocol){
	n=N;

    for(int i=0;i<n;i++)cost[i+1]=confidence[i];

    mins=3; maxs=0;
    for(int i=1;i<=n-1;i++){
        mins=min(mins,protocol[i]);
        maxs=max(maxs,protocol[i]);
    }

    if(mins==maxs and mins==1){
        for(int i=1;i<=n;i++)ans+=cost[i];
        return ans;
    }else if(mins==maxs and mins==2){
        for(int i=1;i<=n;i++)ans=max(ans,cost[i]);
        return ans;
    }

    for(int i=1;i<=n-1;i++){
        if(protocol[i]==0 or protocol[i]==2){
            v[host[i]+1].push_back(i+1);
            v[i+1].push_back(host[i]+1);
        }
        
        if(protocol[i]==1 or protocol[i]==2){
            for(int f:v[host[i]+1]){
                v[f].push_back(i+1);
                v[i+1].push_back(f);
            }
        }
    }

    if(n<=20){
        brute(n,0);
        return ans;
    }else if(mins==maxs and mins==0){
        return ff(0,0,-1);
    }

    source=0; sink=n+1;
    for(int i=1;i<=n;i++){
        if(!li[i])dfs(i,0);
    }

    while(true){
        tim++;
        flow=fordfulk(source);
        if(flow==0)break;
        maxflow+=flow;
    }

    tim++; u[source]=u[sink]=tim;
    for(int i=0;i<g[source].size();i++){
        if(g[source][i].cap and u[g[source][i].to]!=tim){
            dfs2(g[source][i].to);
        }
    }

    for(int i=1;i<=n;i++){
        if(where[i]==0 and u[i]!=tim)mvc++;
        if(where[i]==1 and u[i]==tim)mvc++;
    }
    
    return n-mvc;
}


/*int main(){

    cout<<findSample(9,{1,1,1,1,1,1,1,1,1},{0,0,1,1,3,3,3,6,6},{0,0,0,0,0,0,0,0,0})<<"\n";

	return 0;
}*/

Compilation message (stderr)

friend.cpp: In function 'int fordfulk(int)':
friend.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
friend.cpp: In function 'void dfs2(int)':
friend.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:173:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |     for(int i=0;i<g[source].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~

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