Submission #1029612

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1029612	2024-07-21T06:04:55 Z	Mr_Husanboy	Beech Tree (IOI23_beechtree)	C++17	5 / 100	49 ms	18636 KB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>


#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){
    return a.size();
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

vector<int> beechtree(int n, int m, std::vector<int> par, std::vector<int> col)
{
    vector<vector<int>> g(n);
    for(int i = 1; i < n; i ++){
        g[par[i]].push_back(i);
        col[i] --;
    }

    vector<int> res(n);
    vector<int> cnt(m + 1);
    for(int i = n - 1; i >= 0; i --){
        res[i] = 1;
        if(col[i] != col.back()) break;
    }
    return res;

    auto check = [&](int &node, vector<int> &perm){
        if(perm[0] != node) return false;
        vector<int> f(len(perm));


        for(int i = 1; i < len(perm); i ++){
            f[i] = cnt[col[perm[i]]];
            cnt[col[perm[i]]] ++;
        }
        for(int i = 1; i < len(perm); i ++) cnt[col[perm[i]]] --;
        //debug(f, cnt);
        for(int i = 1; i < len(perm); i ++){
            if(perm[f[i]] != par[perm[i]]) return false;
        }
        return true;
    };  


    auto dfs = [&](auto &dfs, int i)->vector<int>{
        vector<int> perm = {i};
        for(auto u : g[i]){
            auto r = dfs(dfs, u);
            if(len(perm) < len(r)) swap(perm, r);
            for(auto u : r) perm.push_back(u);
        }
        sort(all(perm));
        //debug(perm);
        do{
            if(check(i, perm)){
                res[i] = 1;
                break;
            }
        }while(next_permutation(all(perm)));

        return perm;
    };
    dfs(dfs, 0);
    return res;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	2nd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #1
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	0 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
8	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	48 ms	15980 KB	Output is correct
8	Correct	47 ms	18636 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	1220 KB	Output is correct
14	Correct	1 ms	1372 KB	Output is correct
15	Correct	1 ms	1372 KB	Output is correct
16	Correct	1 ms	1372 KB	Output is correct
17	Correct	46 ms	18128 KB	Output is correct
18	Correct	46 ms	18512 KB	Output is correct
19	Correct	48 ms	18516 KB	Output is correct
20	Correct	49 ms	18620 KB	Output is correct

Subtask #3
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	2nd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

Subtask #5
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	2nd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

Subtask #7
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	2nd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 17.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
4	Halted	0 KB	-

Subtask #9
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	2nd lines differ - on the 2nd token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Submission #1029612

Compilation message