oj.uz

Submission #582411

# Submission time Handle Problem Language Result Execution time Memory
582411 2022-06-23T17:40:55 Z wdjpng Friend (IOI14_friend) C++17
35 / 100
 3 ms 2756 KB 
#include "friend.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()

using namespace std;
int N =1e5+1;

vector<vector<int>>mem(2,vector<int>(N,-1));
vector<vector<int>>E;
vector<int>conf(N);

int dfs(int v, int p, int allow)
{
	if(mem[allow][v]!=-1) return mem[allow][v];

	int s = 0;
	for (int w : E[v]) if(w!=p) s+=dfs(w,v,true);

	int s2=conf[v];
	for (int w : E[v]) if(w!=p) s2+=dfs(w,v,false);

	if(allow) return  mem[allow][v]=max(s2,s);
	return mem[allow][v]=s;
}
// Find out best sample
signed findSample(signed n,signed oorgconf[],signed host[],signed protocol[]){
	vector<int>ops;
	rep(i,n-1) ops.push_back(protocol[i+1]);
	sort(all(ops));
	ops.erase(unique(all(ops)), ops.end());

	vector<int>without(n,0);
	E.assign(n, vector<int>());
	rep(i,n) conf[i]=oorgconf[i];

	if(ops.size()==1)
	{
		int sum=0, maxx=0;
		rep(i,n) maxx=max(maxx,conf[i]);
		for(int x : conf) sum+=x;

		if(ops[0]==1) // my friends are yours
		{
			return sum;
		}
		if(ops[2]) return maxx;
	}

	int best = conf[0];
	for(int st = 1; st < n; st++)
	{
		if(protocol[st]==0)
		{
			// I am friend
			E[host[st]].push_back(st);
		}
	}

	return dfs(0,-1,true);
}

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Incorrect 2 ms 2644 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
8.0 / 8.0

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

Subtask #4
19.0 / 19.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Incorrect 2 ms 2644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Incorrect 3 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -