Submission #1178389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178389		Kaztaev_Alisher	Beech Tree (IOI23_beechtree)	C++20	9 / 100	2123 ms	763540 KiB

beechtree

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

int n , m , p[N] , cnt[N] , c[N];
vector<int> sub[N];
vector<int> solve(){
	for(int i = 1; i <= n; i++){
		int x = p[i];
		while(x > 0){
			sub[x].push_back(i);
			x = p[x];	
		}
	}
	vector<int> ans(n,0);
	for(int v = 1; v <= n; v++){
		sort(all(sub[v]));
		while(next_permutation(all(sub[v]))){
			int ok = 1;
			// cout << v << "\n";
			for(int j = 0; j < sub[v].size(); j++){
				int u = sub[v][j];
				if(cnt[c[u]] == 0){
					if(p[u] != v) ok = 0;
				} else {
					if(p[u] != sub[v][cnt[c[u]]-1]) ok = 0;
				}
				cnt[c[u]]++;
			}
			for(int j = 0; j < sub[v].size(); j++){
				int u = sub[v][j];
				cnt[c[u]]--;
			}
			if(ok == 1){
				ans[v-1] = 1;
			}
		}
		if(1){
			sort(all(sub[v]));
			int ok = 1;
			for(int j = 0; j < sub[v].size(); j++){
				int u = sub[v][j];
				if(cnt[c[u]] == 0){
					if(p[u] != v) ok = 0;
				} else {
					if(p[u] != sub[v][cnt[c[u]]-1]) ok = 0;
				}
				cnt[c[u]]++;
			}
			for(int j = 0; j < sub[v].size(); j++){
				int u = sub[v][j];
				cnt[c[u]]--;
			}
			if(ok == 1){
				ans[v-1] = 1;
			}
		}
		if(sub[v].size() == 0) ans[v-1] = 1;
	}
	return ans;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
	n = N; m = M;
	for(int i = 0; i < P.size(); i++){
		p[i+1] = P[i]+1;
		c[i+1] = C[i];
	}
	return solve();
}
// 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;
// }
// 

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 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