Submission #742225

#	Time	Username	Problem	Language	Result	Execution time	Memory
742225		angels	Friend (IOI14_friend)	C++14	0 / 100	16 ms	22128 KiB

friend

#include <bits/stdc++.h>

using namespace std;
vector<int> a[100000];
bool visited[100000];
int dfs(int x, int val, int n, int confidence[])
{
    int rez=0, i=0;
    if(x==n)
        return val;
    for(i=a[x].size(); i--;)
    {
        if(visited[a[x][i]]==true)
            break;
    }
    if(i<0)
    {
        visited[x]=1;
        rez=dfs(x+1, val+confidence[x], n, confidence);
    }
    visited[x]=false;
    int v=dfs(n+1, val, n, confidence);
    if(v>rez)
        rez=v;
    return v;
}

int subtask1(int n, int confidence[], int host[], int protocol[])
{
    for(int i=1; i<n; i++)
    {
        if(protocol[i]==0)
        {
            a[host[i]].push_back(i);
            a[i].push_back(host[i]);
        }
        if(protocol[i]==1)
        {
            for(int j=a[host[i]].size(); j>0; j--)
            {
                a[a[host[i]][j]].push_back(i);
                a[i].push_back(a[host[i]][j]);
            }
        }
        if(protocol[i]==2)
        {
            a[host[i]].push_back(i);
            a[i].push_back(host[i]);
            for(int j=a[host[i]].size(); j>0; j--)
            {
                a[a[host[i]][j]].push_back(i);
                a[i].push_back(a[host[i]][j]);
            }
        }
    }
    return dfs(0, 0, n, confidence);
}

int findSample(int n,int confidence[],int host[],int protocol[])
{
    int i, w;
    //cin>>n;
    //int confidence[n], host[n], protocol[n];
    if(n<=10)
    {
        w=subtask1(n, confidence, host, protocol);
        return(w);
    }
    for(i=1; i<n; i++)
    {
        if(protocol[i-1]!=protocol[i])
            break;
    }
    if(i==n)
    {
        if(protocol[0]==1)
        {
            w=0;
            for(int j=0; j<n; j++)
            {
                w+=confidence[i];
            }
        }
        else if(protocol[0]==2)
        {
            w=-1;
            for(i=0; i<n; i++)
            {
                if(confidence[i]>w)
                    w=confidence[i];
            }
        }
    }
    //cout<<w;
    return(w);
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:61:12: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     int i, w;
      |            ^

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