Submission #844171

#	Time	Username	Problem	Language	Result	Execution time	Memory
844171		MrBrionix	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2123 ms	772420 KiB

beechtree

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200'000;
vector<pair<int, int>> grafo[MAXN], opz[MAXN];
int m, col[MAXN], p[MAXN];
bool ok[MAXN];
/*
void dfs(int nodo) {

	ok[nodo] = false;
	for (auto [to, c] : grafo[nodo]) {
		dfs(to);

		opz[nodo].emplace_back(to, c);
		for (auto [nod, c] : opz[to]) {
			opz[nodo].emplace_back(nod, c);
		}
	}

	sort(opz[nodo].begin(), opz[nodo].end());

	do {
		vector<int> cont(m + 1, 0);
		auto tmp = opz[nodo];
		tmp.insert(tmp.begin(), {nodo, 0});

		bool flag = true;
		for (int i = 1; i < tmp.size(); i++) {
			if (tmp[cont[tmp[i].second]].first != p[tmp[i].first])flag = false;

			cont[tmp[i].second]++;
		}

		ok[nodo] |= flag;

	} while (next_permutation(opz[nodo].begin(), opz[nodo].end()));
	//cout<<nodo<<" "<<col[nodo]<<"\n";
}
*/


map<int,int> freq[MAXN];
int num[MAXN];

bool comp(pair<int,int> x,pair<int,int> y){
    return num[x.first]>num[y.first];
}

void dfs(int nodo){
    
    vector<int> tmp;
    for(auto [to,c] : grafo[nodo]){
        dfs(to);
        
        num[nodo]+=num[to]+1;
        tmp.push_back(c);
        
        freq[nodo][c]++;
    }
    
    sort(tmp.begin(),tmp.end());
    sort(grafo[nodo].begin(),grafo[nodo].end(),comp);
    
    ok[nodo]=true;
    for(int i=1;i<tmp.size();i++){
        if(tmp[i]==tmp[i-1])ok[nodo]=false;
    }
    
    for(int i=0;i<grafo[nodo].size();i++){
        int curr = grafo[nodo][i].first;
        int prev = (i==0 ? nodo : grafo[nodo][i-1].first);
        
        for(auto [x,y] : freq[curr]){
            if(y>freq[prev][x])ok[nodo]=false;
        }
    }
    
    
    for(auto [to,c] : grafo[nodo]){
        for(auto [x,y] : freq[to]){
            freq[nodo][x]+=y;
        }
    }
    
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
	m = M;
	for (int i = 1; i <= N - 1; i++) {
		grafo[P[i]].emplace_back(i, C[i]);
		p[i] = P[i];
	}

	dfs(0);

	vector<int> ans;
	for (int i = 0; i < N; i++) {
		ans.push_back(ok[i]);
	}
	return ans;
}
/*

int main() {
	int N, M;
	assert(2 == scanf("%d %d", &N, &M));
	std::vector<int> P(N);
	for (int i = 0; i < N; ++i)
		assert(1 == scanf("%d", &P[i]));
	std::vector<int> C(N);
	for (int i = 0; i < N; ++i)
		assert(1 == scanf("%d", &C[i]));

	fclose(stdin);

	std::vector<int> res = beechtree(N, M, P, C);

	int n = res.size();
	for (int i = 0; i < n; ++i) {
		if (i > 0)
			printf(" ");
		printf("%d", res[i]);
	}
	printf("\n");
	fclose(stdout);

	return 0;
}
*/

Compilation message (stderr)

beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=1;i<tmp.size();i++){
      |                 ~^~~~~~~~~~~
beechtree.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<grafo[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 9 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12