#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(v) (ll)(v.size())
// TO INCREASE STACK SIZE !
static void run_with_stack_size(void (*func)(void), size_t stsize) {
char *stack, *send;
stack = (char *)malloc(stsize);
send = stack + stsize - 16;
send = (char *)((uintptr_t)send / 16 * 16);
asm volatile(
"mov %%esp, (%0)\n"
"mov %0, %%esp\n"
:
: "r"(send));
func();
asm volatile("mov (%0), %%esp\n" : : "r"(send));
free(stack);
}
ll n;
vector<ll> parent, outdeg, freq;
set<ll> candidates;
vector<vector<ll>> g;
vector<set<ll>> page;
vector<map<ll, ll>> dp;
map<string, ll> mp;
void solve() {
cin >> n;
// reset after each testcase
ll ans = 0;
candidates.clear(), mp.clear();
parent = outdeg = vector<ll>(n+1);
g = vector<vector<ll>>(n+1);
page = vector<set<ll>>(n+1);
dp = vector<map<ll, ll>>(n+1);
// input
for(ll i=2; i<=n; ++i)
cin >> parent[i],
outdeg[parent[i]]++,
g[parent[i]].push_back(i);
// Edges are directed from parent to their children
for(ll i=1; i<=n; ++i){
ll m; cin >> m;
while(m--){
string topic; cin >> topic;
if(mp.find(topic) == mp.end()) mp[topic] = sz(mp)+1;
page[i].insert(mp[topic]);
// page[i] is a "set" because we don't care about repeated topics on single page
}
}
freq = vector<ll>(sz(mp)+5);
queue<ll> q;
for(ll i=1; i<=n; ++i) if(!outdeg[i]) q.push(i); // pushing all leaves in queue
for(ll i=1; i<=n; ++i){
for(auto topic: page[i]){
freq[topic]++;
if(freq[topic] >= sz(q)) candidates.insert(topic);
// only those topics are potential candidates whose frequencies exceed no. of leaves (no. of leaves was equal to size of queue)
}
}
/* DP(nn, topic) = 0 (a partition of subtreee "nn" exists such that we need one "topic"), 1 (a partition of subtreee "nn" exists such that we need no "topic"), -1 ("topic" can't be the answer)
Start from all way down from leaves. For each potential candidate(topic), for the current node, lets say "nn", iterate through all the children and calc DP(nn, topic).
Push the node with outdeg = 0;
*/
while(!q.empty()){
ll nn = q.front(); q.pop();
for(auto topic: candidates){
ll c=0, poss=1;
for(auto v: g[nn])
c += (dp[v][topic] == 0),
poss &= (dp[v][topic] >= 0);
poss &= (c <= 1);
if(poss)
dp[nn][topic] = page[nn].count(topic) || (sz(g[nn]) && !c);
else
dp[nn][topic] = -1;
}
outdeg[parent[nn]]--;
if(!outdeg[parent[nn]]) q.push(parent[nn]);
}
for(auto topic: candidates)
ans += (dp[1][topic] == 1);
cout << ans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("wiki_race_input.txt", "r", stdin);
freopen("out.txt", "w", stdout);
ll t=1;
cin >> t;
for (ll i = 0; i < t; i++) {
cout << "Case #" << i + 1 << ": ";
// solve();
run_with_stack_size(solve, 1024*1024*1024);
cout << '\n';
}
}
Your program needs too much time.
Consider a tree that is just a line. It will only have one leave. So every topic will be a candidate. And for every node in the tree you will iterate over all topics. Which will take too long, if there are 1,000,000 nodes and 8,000,000 topics. (Also it will probably not fit into memory).
Oh, I see. I guess I'll have to handle the computation for the node with a single child separately. Is that correct? Is there any optimization you can suggest?
The official solution uses the same approach as you. There you can find the optimization you need to make.
Ok. Thanks for the help.