oj.uz

Submission #385987

# Submission time Handle Problem Language Result Execution time Memory
385987 2021-04-05T10:30:31 Z mehrdad_sohrabi Friend (IOI14_friend) C++14
100 / 100
 48 ms 9452 KB 
// Black lives matter
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=1e5+10;
ll val[N];
ll s[N];
ll jam[N];
ll par[N];
vector <pii> g[N];
ll dp[N][2];
/// 0 varnadare 1 vardare

int32_t findSample(int32_t n,int32_t confidence[],int32_t host[],int32_t protocol[]){
	for (int i=0;i<n;i++) val[i]=confidence[i],par[i]=i,dp[i][1]=val[i];
	for (int i=1;i<n;i++){
            /// 0 yal adi
            /// 1 yal tosi
            /// 2 yal ghermez
        if (protocol[i]==0){
            g[par[host[i]]].pb({i,protocol[i]});
        }
        if (protocol[i]){
            par[i]=par[host[i]];
            g[host[i]].pb({i,protocol[i]});
        }
	}
//	for (int i=1;i<n;i++) cout << protocol[i] << " ";
	//cout << endl;
	for (int i=n-1;i>0;i--){
        if (protocol[i]==0){
            dp[host[i]][0]+=max(dp[i][1],dp[i][0]);
            dp[host[i]][1]+=dp[i][0];
            continue;
        }
        if (protocol[i]==1){
        //if (host[i]==1) cout << i << " " << dp[1][1] << " " << dp[1][0] << " " << dp[i][1] << " " << dp[i][0] << endl;
            dp[host[i]][1]=max(dp[host[i]][0]+dp[i][1],max(dp[host[i]][1]+dp[i][1],dp[host[i]][1]+dp[i][0]));
            dp[host[i]][0]+=dp[i][0];
         //   dp[host[i]][1]=max(dp[host[i]][1],dp[host[i]][0]+dp[i][0]);
            continue;
        }
        dp[host[i]][1]=max(dp[host[i]][1]+dp[i][0],dp[host[i]][0]+dp[i][1]);
        dp[host[i]][0]+=dp[i][0];
        
	}
	//cout << dp[1][1] << endl;
	return max(dp[0][0],dp[0][1]);
}
/*
// Confidence
int32_t confidence[N];

// Host
int32_t host[N];


int32_t protocol[N];

// Main
int32_t main(void)
{
	int n,i;

	// Number of people
	assert(scanf("%d",&n)==1);

	// Confidence
	for(i=0;i<n;i++)
		assert(scanf("%d",&confidence[i])==1);

	// Host and Protocol
	for(i=1;i<n;i++){
		scanf("%d %d",&host[i],&protocol[i]);
		//cout << protocol[i] << endl;
	}
	// Answer
	printf("%d\n",findSample(n,confidence,host,protocol));
	return 0;
}
*/

Subtask #1
11.0 / 11.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 4 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 4 ms 2796 KB Output is correct

Subtask #4
19.0 / 19.0

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

Subtask #5
23.0 / 23.0

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

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2668 KB Output is correct
7 Correct 3 ms 2668 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Correct 3 ms 2668 KB Output is correct
10 Correct 4 ms 2668 KB Output is correct
11 Correct 3 ms 2668 KB Output is correct
12 Correct 48 ms 9452 KB Output is correct
13 Correct 24 ms 6124 KB Output is correct
14 Correct 41 ms 8812 KB Output is correct
15 Correct 41 ms 8812 KB Output is correct