Submission #1066070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066070		Zicrus	Beech Tree (IOI23_beechtree)	C++17	58 / 100	2070 ms	86600 KiB

beechtree

#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
 
typedef long long ll;

ll n;
vector<int> c;
vector<int> res;
vector<vector<ll>> adj;
vector<unordered_map<ll, ll>> adjSet;
vector<bool> mult;
unordered_map<ll, bool> cache;

bool subset(int a, int b) {
    ll hash = ((ll)a << 31) | (ll)b;
    if (cache.count(hash)) return cache[hash];
    for (auto &e : adjSet[a]) {
        int i = e.second;
        if (!adjSet[b].count(c[i])) return cache[hash] = false;
        if (!subset(i, adjSet[b][c[i]])) return cache[hash] = false;
    }
    return cache[hash] = true;
}

vector<pair<int, int>> dfsSol(int cur) {
    bool beautiful = !mult[cur];
    vector<pair<int, int>> arr;
    for (auto &e : adj[cur]) {
        auto tmp = dfsSol(e);
        arr.insert(arr.end(), tmp.begin(), tmp.end());
        beautiful &= res[e];
    }
    arr.push_back({arr.size()+1, cur});
    sort(arr.begin(), arr.end());
    if (!beautiful) return arr;
    
    for (int i = 1; i < arr.size(); i++) {
        if (!subset(arr[i-1].second, arr[i].second)) return arr;
    }
    res[cur] = 1;
    return arr;
}
 
vector<int> beechtree(int n1, int m, vector<int> p, vector<int> c1) {
    n = n1; c = c1;
    res = vector<int>(n);
    adj = vector<vector<ll>>(n);
    adjSet = vector<unordered_map<ll, ll>>(n);
    mult = vector<bool>(n);
    for (int i = 1; i < n; i++) {
        if (adjSet[p[i]].count(c[i])) mult[p[i]] = true;
        else adjSet[p[i]][c[i]] = i;

        adj[p[i]].push_back(i);
    }
    
    dfsSol(0);
    return res;
}

/*
For each subtree:
beautiful if:
- (All children are beautiful)
- All subtrees ordered by total size are subsets of each other
*/

#ifdef TEST
#include "grader.cpp"
#endif

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<std::pair<int, int> > dfsSol(int)':
beechtree.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 1; i < arr.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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