| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115334 |
2019-06-06T17:24:53 Z |
faustaadp |
Friend (IOI14_friend) |
C++17 |
|
62 ms |
9188 KB |
#include "friend.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
// Find out best sample
ll i,n,b[3],a[101010],jum,ma,x[2],has,j,k;
vector<ll> v[101010];
ll vis[101010];
ll mat[101010];
ll d[101010][2];
ll udh[1010][1010];
ll ada[1010];
ll dfs(ll aa)
{
if(vis[aa])
return 0;
vis[aa]=1;
ll ii;
for(ii=0;ii<v[aa].size();ii++)
if(mat[v[aa][ii]]==-1||dfs(mat[v[aa][ii]]))
{
mat[v[aa][ii]]=aa;
return 1;
}
return 0;
}
ll depe(ll aa,ll bb,ll cc)
{
if(d[aa][bb]==-1)
{
ll ii,h1=a[aa],h2=0;
for(ii=0;ii<v[aa].size();ii++)
{
if(v[aa][ii]==cc)continue;
h1+=depe(v[aa][ii],1,aa);
h2+=depe(v[aa][ii],0,aa);
}
d[aa][bb]=max(h1,h2);
if(bb)
d[aa][bb]=h2;
}
return d[aa][bb];
}
int findSample(int n,int confidence[],int host[],int protocol[])
{
//int ans=10;
for(i=0;i<n;i++)
{
if(i>=1)
{
b[protocol[i]]=1;
if(protocol[i]==0)
{
if(!udh[host[i]][i])
{
v[host[i]].pb(i);
v[i].pb(host[i]);
// cout<<i<<" "<<i<<" "<<host[i]<<"\n";
udh[i][host[i]]=1;
udh[host[i]][i]=1;
}
}
else
if(protocol[i]==1)
{
for(j=0;j<v[host[i]].size();j++)
{
if(udh[i][v[host[i]][j]])continue;
// cout<<i<<" "<<v[host[i]][j]<<" "<<i<<"\n";
v[v[host[i]][j]].pb(i);
v[i].pb(v[host[i]][j]);
udh[i][v[host[i]][j]]=1;
udh[v[host[i]][j]][i]=1;
}
}
else
//if(n<=10)
{
for(j=0;j<v[host[i]].size();j++)
{
if(udh[i][v[host[i]][j]])continue;
// cout<<i<<" "<<v[host[i]][j]<<" "<<i<<"\n";
v[v[host[i]][j]].pb(i);
v[i].pb(v[host[i]][j]);
udh[i][v[host[i]][j]]=1;
udh[v[host[i]][j]][i]=1;
}
if(!udh[host[i]][i])
{
v[host[i]].pb(i);
v[i].pb(host[i]);
// cout<<i<<" "<<i<<" "<<host[i]<<"\n";
udh[i][host[i]]=1;
udh[host[i]][i]=1;
}
}
}
a[i]=confidence[i];
jum+=a[i];
ma=max(ma,a[i]);
}
/*if(b[0]==0&&b[1]==1&&b[2]==0)
return jum;
if(b[0]==0&&b[1]==0&&b[2]==1)
return ma;
if(b[0]==1&&b[1]==0&&b[2]==0)
{
memset(d,-1,sizeof(d));
return depe(0,0,0);
}
if(n<=10)
{
for(i=0;i<(1<<n);i++)
{
ll hz=0;
for(j=0;j<n;j++)
if(i&(1<<j))
{
hz+=a[j];
ada[j]=1;
}
else
ada[j]=0;
for(j=0;j<n;j++)
for(k=0;k<v[j].size();k++)
if(ada[j]&&ada[v[j][k]])
{
// cout<<i<<" "<<j<<" "<<v[j][k]<<"\n";
hz=0;
break;
}
has=max(has,hz);
}
return has;
}*/
//if(b[0]==1&&b[1]==1&&b[2]==0)
{
memset(mat,-1,sizeof(mat));
// has=n;
for(i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
has+=dfs(i);
// if(v[i].empty())
// has++;
}
//has=n-has;
return has;
}
}
Compilation message
friend.cpp: In function 'll dfs(ll)':
friend.cpp:23:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
friend.cpp: In function 'll depe(ll, ll, ll)':
friend.cpp:36:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ii=0;ii<v[aa].size();ii++)
~~^~~~~~~~~~~~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:70:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[host[i]].size();j++)
~^~~~~~~~~~~~~~~~~~
friend.cpp:83:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[host[i]].size();j++)
~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
9188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
