Submission #995527

#	Time	Username	Problem	Language	Result	Execution time	Memory
995527		mindiyak	September (APIO24_september)	C++17	0 / 100	1 ms	348 KiB

september

#include "september.h"

#include <vector>
#include <iostream>
#include <set>  

using namespace std;

vector<vector<int>> sons;
vector<int> flagged;
vector<int> removed;
vector<int> parent;
set<int> to_be_removed;

bool check_sons(int pos){
	bool a = true;
	for(int i=0;i<sons[pos].size();i++){
		if(removed[sons[pos][i]] == 0){
			a = false;
			to_be_removed.insert(sons[pos][i]);
			// cout << "to_be_removed - add - " << sons[pos][i] << endl;
		}
	}
	return a;
}

void remove_parents(int pos){
	if(flagged[parent[pos]] == 0)return;
	if(check_sons(parent[pos])){
		removed[parent[pos]] = 1;
		// cout << "to_be_removed - remove - " << parent[pos] << endl;
		if(to_be_removed.count(parent[pos])){
			to_be_removed.erase(parent[pos]);
		}
		remove_parents(parent[pos]);
	}
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	sons.resize(N,vector<int>());
	removed.resize(N,0);
	flagged.resize(N,0);
	parent.resize(N,0);
	to_be_removed.clear();

	for(int i=1;i<N;i++){
		sons[F[i]].push_back(i);
		parent[i] = F[i];
	}

	int ans = 0;
	for(int i=0;i<N-1;i++){
		bool check = check_sons(S[0][i]);
		// cout << "to_be_removed - remove - " << S[0][i] << endl;
		if(to_be_removed.count(S[0][i])){
			to_be_removed.erase(S[0][i]);
		}
		// for (auto it = to_be_removed.begin(); it !=to_be_removed.end(); ++it)
        // 	cout << ' ' << *it;
		// cout << endl;
		// cout << S[0][i] << " " << check << " " << to_be_removed.empty() << endl;
		if(check){
			removed[S[0][i]] = 1;
			remove_parents(S[0][i]);
			if(to_be_removed.empty()){
				ans ++;
			}
		}else{
			flagged[S[0][i]] = 1;
		}

		// for(int j=0;j<N;j++)cout<<removed[j] << " ";
		// cout << endl;
		// for(int j=0;j<N;j++)cout<<flagged[j] << " ";
		// cout << endl;
	}

	return ans;
}

Compilation message (stderr)

september.cpp: In function 'bool check_sons(int)':
september.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<sons[pos].size();i++){
      |              ~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16