Submission #1064494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064494		anango	Friend (IOI14_friend)	C++17	100 / 100	19 ms	4728 KiB

friend

#include "friend.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define mex max

int INF = 1LL<<60;
// Find out best sample
signed findSample(signed n,signed confidence[],signed host[],signed protocol[]){
	int ans=10;
    //let 0 denote i, 1 denote the friends of i
    //let dp0[i] = answer if we are allowed 0 or 1
    //dp1[i] = answer if we're only allowed 0
    //dp2[i] = answer if we're only allowed 1
    //dp3[i] = answer if we're allowed neither
    //in the subtree of i
    //actually, 
    //dp0[i] = answer if we didn't use any friends of i so far
    //dp1[i] = answer if we did use some friend of i so far
    //no it doesn't work
    //dp0[i] = answer if we didn't use i
    //dp1[i] = answer if we did use i


    vector<int> dp0(n,0);
    vector<int> dp1;
    for (int i=0; i<n; i++) dp1.push_back(confidence[i]);
    for (int i=n-1; i>=1; i--) {
        int parent = host[i];
        int jambloooooooooatautautau = protocol[i];
        int x = dp0[parent];
        int y = dp1[parent];
        int z = dp0[i];
        int w = dp1[i];
        int newx = -INF;
        int newy = -INF;
        if (jambloooooooooatautautau==0) {
            newx=x+w;
            newy=y+z;
        }
        else if (jambloooooooooatautautau==1) {
            newx=x+z;
            newy=y+w;
        }
        else if (jambloooooooooatautautau==2) {
            newx=x+z;
            newy=max(y+z,x+w);
        }
        dp0[parent] = newx; 
        dp1[parent] = newy;
        dp1[parent]=max(dp0[parent],dp1[parent]);
        //cout << "transition " << jambloooooooooatautautau <<" " << i <<" " << x<< " " << y <<" " <<z <<" " << w <<" " << newx <<" " << newy << endl;
    }
    for (int i=0; i<n; i++) {
        //cout << i <<" " << dp0[i] <<" " << dp1[i] << endl;
    }
    int mans = max(dp0[0],dp1[0]);
	return mans;
}

Compilation message (stderr)

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:10:6: warning: unused variable 'ans' [-Wunused-variable]
   10 |  int ans=10;
      |      ^~~

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 31 / 31