# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
589412 |
2022-07-04T15:51:14 Z |
yutabi |
Friend (IOI14_friend) |
C++14 |
|
26 ms |
2668 KB |
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
bool graph[1003][1003];
int subtask1(int n,int confidence[],int host[],int protocol[])
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
graph[i][j]=0;
}
}
for(int i=1;i<n;i++)
{
if(protocol[i]!=0)
{
for(int j=0;j<n;j++)
{
if(graph[host[i]][j])
{
graph[j][i]=graph[i][j]=1;
}
}
}
if(protocol[i]!=1)
{
graph[host[i]][i]=graph[i][host[i]]=1;
}
}
int ans=0;
for(int i=0;i<1<<n;i++)
{
vector <int> nums;
int curr=0;
for(int j=0,k=i;k;j++,k/=2)
{
if(k%2)
{
nums.pb(j);
curr+=confidence[j];
}
}
bool flag=0;
for(int j=0;j<nums.size();j++)
{
for(int k=0;k<nums.size();k++)
{
if(graph[nums[j]][nums[k]])
{
flag=1;
}
}
}
if(!flag)
{
ans=max(ans,curr);
}
}
return ans;
}
int subtask2(int n,int confidence[],int host[],int protocol[])
{
int ans=0;
for(int i=0;i<n;i++)
{
ans+=confidence[i];
}
return ans;
}
int subtask3(int n,int confidence[],int host[],int protocol[])
{
int ans=0;
for(int i=0;i<n;i++)
{
ans=max(ans,confidence[i]);
}
return ans;
}
int DP[1003][2];
int* con;
void DFS(int node,int parent)
{
int ans1=0;
int ans2=0;
for(int i=0;i<1003;i++)
{
if(graph[node][i] && i!=parent)
{
DFS(i,node);
ans1+=DP[i][0];
ans2+=DP[i][1];
}
}
ans1+=con[node];
ans1=max(ans1,ans2);
DP[node][0]=ans2;
DP[node][1]=ans1;
}
int subtask4(int n,int confidence[],int host[],int protocol[])
{
con=confidence;
for(int i=0;i<1003;i++)
{
for(int j=0;j<1003;j++)
{
graph[i][j]=0;
}
}
for(int i=1;i<n;i++)
{
if(protocol[i]!=0)
{
for(int j=0;j<n;j++)
{
if(graph[host[i]][j])
{
graph[j][i]=graph[i][j]=1;
}
}
}
if(protocol[i]!=1)
{
graph[host[i]][i]=graph[i][host[i]]=1;
}
}
DFS(0,-1);
return DP[0][1];
}
int findSample(int n,int confidence[],int host[],int protocol[])
{
/*if(n<=10)
{
return subtask1(n,confidence,host,protocol);
}
if(protocol[1]==1)
{
return subtask2(n,confidence,host,protocol);
}
if(protocol[1]==2)
{
return subtask3(n,confidence,host,protocol);
}
if(protocol[1]==0)
{
return subtask4(n,confidence,host,protocol);
}
bool oopsie=0;
assert(oopsie);*/
int ans=0;
for(int i=n-1;i>=0;i--)
{
if(protocol[i]==0)
{
ans+=confidence[i];
confidence[host[i]]-=confidence[i];
confidence[host[i]]=max(confidence[host[i]],0);
}
if(protocol[i]==1)
{
confidence[host[i]]+=confidence[i];
}
if(protocol[i]==2)
{
confidence[host[i]]=max(confidence[host[i]],confidence[i]);
}
}
ans+=confidence[0];
return ans;
}
Compilation message
friend.cpp: In function 'int subtask1(int, int*, int*, int*)':
friend.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int j=0;j<nums.size();j++)
| ~^~~~~~~~~~~~
friend.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int k=0;k<nums.size();k++)
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
308 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
312 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
320 KB |
Output is correct |
6 |
Correct |
1 ms |
308 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
312 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
308 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
26 ms |
2668 KB |
Output is correct |
13 |
Correct |
12 ms |
1452 KB |
Output is correct |
14 |
Correct |
21 ms |
2400 KB |
Output is correct |
15 |
Correct |
22 ms |
2380 KB |
Output is correct |