# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
798360 |
2023-07-30T16:00:40 Z |
Khizri |
Friend (IOI14_friend) |
C++17 |
|
31 ms |
65536 KB |
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1005;
int n,arr[mxn],rel[mxn][mxn],ans=0,dp[mxn][2];
vector<int>vt[mxn];
void dfs(int u,int p){
for(int v:vt[u]){
if(v!=p){
dfs(v,u);
dp[u][0]+=dp[v][1];
dp[u][1]+=dp[v][0];
}
}
dp[u][0]+=arr[u];
ans=max(ans,dp[u][0]);
ans=max(ans,dp[u][1]);
}
int findSample(int N,int confidence[],int host[],int protocol[]){
n=N;
for(int i=0;i<n;i++){
arr[i+1]=confidence[i];
}
bool task2=true,task3=true,task4=true;
for(int i=1;i<n;i++){
int type=protocol[i];
if(type!=1) task2=false;
if(type!=2) task3=false;
if(type!=0) task4=false;
}
if(task2){
int mx=0;
for(int i=1;i<=n;i++){
mx+=arr[i];
}
return mx;
}
if(task3){
int mx=0;
for(int i=1;i<=n;i++){
mx=max(mx,arr[i]);
}
return mx;
}
for(int i=1;i<n;i++){
int node=host[i]+1;
int type=protocol[i];
if(type==0){
vt[node].pb(i+1);
vt[i+1].pb(node);
}
else if(type==1){
int sz=vt[node].size();
for(int j=0;j<sz;j++){
int v=vt[node][j];
vt[v].pb(i+1);
vt[i+1].pb(v);
}
}
else{
int sz=vt[node].size();
for(int j=0;j<sz;j++){
int v=vt[node][j];
vt[v].pb(i+1);
vt[i+1].pb(v);
}
vt[node].pb(i+1);
vt[i+1].pb(node);
}
}
ans=0;
dfs(1,-1);
return ans;
}
// g++ friend.cpp grader.cpp ; .\a.exe
/*
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
*/
Compilation message
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:35:32: warning: variable 'task4' set but not used [-Wunused-but-set-variable]
35 | bool task2=true,task3=true,task4=true;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
352 KB |
Output is correct |
7 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
244 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 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 |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Runtime error |
31 ms |
65536 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |