oj.uz

Submission #1066995

# Submission time Handle Problem Language Result Execution time Memory
1066995 2024-08-20T09:24:57 Z LittleOrange Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 40900 KB 
#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct obj{
    ll i,d;
    set<ll> s;
    bool operator<(const obj &o){
        return d!=o.d?d<o.d:s.size()>o.s.size();
    }
    bool nxt(const obj &o){
        for(ll i : o.s){
            if (!s.count(i)){
                return false;
            }
        }
        return true;
    }
};
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    ll n = N;
    ll m = M;
    vector<vector<ll>> ch(n);
    for(ll i = 1;i<n;i++) ch[P[i]].push_back(i);
    vector<ll> h(n,0),d(n,0);
    {
        function<void(ll)> dfs;
        dfs = [&](ll i){
            for(ll j : ch[i]) {
                d[j] = d[i]+1;
                dfs(j);
                h[i] = max(h[i],h[j]+1);
            }
        };
        dfs(0);
    }
    vector<ll> bad(n,0);
    for(ll i = n-1;i>=0;i--){
        vector<ll> v;
        for(ll j : ch[i]){
            if (bad[j]) bad[i] = 1;
            v.push_back(C[j]);
            if(ch[i].size()<ch[j].size()) bad[i] = 1;
        }
        sort(v.begin(),v.end());
        if (unique(v.begin(),v.end())!=v.end()) bad[i] = 1;
    }
    vector<ll> ans(n,0);
    for(ll i = 0;i<n;i++){
        if (bad[i]) continue;
        if (h[i]<=1) {
            ans[i] = 1;
            continue;
        }
        /*vector<obj> cur;
        function<void(ll)> dfs;
        dfs = [&](ll i){
            if (ch[i].empty()) return;
            obj o = {i,d[i]};
            for(ll j : ch[i]){
                o.s.insert(C[j]);
            }
            cur.push_back(o);
            for(ll j : ch[i]){
                dfs(j);
            }
        };
        dfs(i);
        sort(cur.begin(),cur.end());
        ll res = 1;
        for(ll i = 0;i+1<cur.size();i++){
            if (!cur[i].nxt(cur[i+1])){
                res = 0;
                break;
            }
        }
        ans[i] = res;*/
        ll ok = 1;
        vector<ll> v;
        function<void(ll)> dfs;
        dfs = [&](ll i){
            v.push_back(i);
            for(ll j : ch[i]){
                dfs(j);
            }
        };
        dfs(i);
        ll cur = 0;
        do{
            map<ll,ll> cnt;
            ll y = 1;
            for(ll i = 1;i<v.size();i++){
                if (v[cnt[C[v[i]]]]!=P[v[i]]) y = 0;
                cnt[C[v[i]]]++;
            }
            cur |= y;
        }while(next_permutation(v.begin()+1,v.end()));
        ans[i] = cur;
    }
    return ans;
}

Compilation message

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:93:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             for(ll i = 1;i<v.size();i++){
      |                          ~^~~~~~~~~
beechtree.cpp:79:12: warning: unused variable 'ok' [-Wunused-variable]
   79 |         ll ok = 1;
      |            ^~
beechtree.cpp:23:8: warning: unused variable 'm' [-Wunused-variable]
   23 |     ll m = M;
      |        ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2028 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #1
9.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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct

Subtask #2
0.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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Execution timed out 2096 ms 40900 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
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 Execution timed out 2078 ms 436 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2096 ms 40900 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2028 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Execution timed out 2031 ms 600 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2028 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Execution timed out 2031 ms 600 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2028 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -