oj.uz

Submission #798904

# Submission time Handle Problem Language Result Execution time Memory
798904 2023-07-31T06:47:21 Z Khizri Friend (IOI14_friend) C++17
100 / 100
 23 ms 8456 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=2e5+5;
int n,arr[mxn],ans=0,p[mxn],q[mxn];
vector<int>vt[mxn];
int findSample(int N,int confidence[],int host[],int protocol[]){
	n=N;
    for(int i=0;i<n;i++){
        arr[i+1]=confidence[i];
    }
    for(int i=1;i<=n;i++){
        p[i]=arr[i];
        q[i]=0;
    }
    for(int i=n-1;i>=1;i--){
        int u=host[i]+1;
        int type=protocol[i];
        int v=i+1;
        if(type==0){
            p[u]=p[u]+q[v];
            q[u]=max(q[u]+p[v],q[u]+q[v]);
        }
        else if(type==1){
            p[u]=max({p[u]+p[v],p[u]+q[v],q[u]+p[v]});
            q[u]=q[u]+q[v];
        }
        else{
            p[u]=max(p[u]+q[v],q[u]+p[v]);
            q[u]=q[u]+q[v];
        }
    }
    return max(p[1],q[1]);
}
/*
g++ friend.cpp grader.cpp ; .\a.exe
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
6
1 1 1 1 1 1
0 0
0 0 
1 0
1 0
1 1 
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 2 ms 4924 KB Output is correct
3 Correct 2 ms 5008 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5008 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5012 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5008 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 2 ms 5008 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 5016 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 5048 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 5004 KB Output is correct
7 Correct 2 ms 5008 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5032 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4976 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5012 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 3 ms 5016 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 5012 KB Output is correct
10 Correct 3 ms 5008 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 5012 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5004 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 5012 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 3 ms 5016 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 23 ms 8456 KB Output is correct
13 Correct 12 ms 6740 KB Output is correct
14 Correct 21 ms 8080 KB Output is correct
15 Correct 21 ms 8088 KB Output is correct