#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 2e5 + 5;
vector<ll> v[NN];
vector<ll> col[NN];
ll ada[NN];
ll jum[NN];
ll idd[NN];
ll war[NN];
ll par[NN];
ll m;
vector<pair<vector<ll>, vector<ll> > > glob;
ll te;
void dfs(ll pos, ll dpt)
{
vector<ll> tmp;
tmp.pb(-col[pos].size());
tmp.pb(-dpt);
tmp.pb(pos);
// cout << pos << " POS\n";
glob.pb(mp(tmp, col[pos]));
for(auto nx : v[pos])
dfs(nx, dpt + 1);
}
ll unik(vector<ll> X)
{
sort(X.begin(), X.end());
for(ll i = 1; i < X.size(); i++)
if(X[i - 1] == X[i])
return 0;
return 1;
}
ll d[NN];
ll cari(ll pos)
{
ll &ret = d[pos];
if(ret != -1)
return ret;
ret = 1;
for(auto nx : v[pos])
if(!cari(nx))
{
ret = 0;
break;
}
if(!ret)return ret;
if(!unik(col[pos]))ret = 0;
if(!ret)return ret;
glob.clear();
// cout << pos << " @@@\n";
dfs(pos, 1);
sort(glob.begin(), glob.end());
do
{
ret = 0;
// if(pos == 0)cout << "\n";
ll oi = 1;
for(ll i = 1; i <= m; i++)
jum[i] = 0;
for(ll i = 0; i < glob.size(); i++)
idd[glob[i].fi[2]] = 0;
for(ll i = 0; i < glob.size(); i++)
{
// if(pos == 0)cout << glob[i].fi[2] << " _\n";
if(i == 0)
continue;
if(idd[par[glob[i].fi[2]]] != jum[war[glob[i].fi[2]]])
{
oi = 0;
break;
}
jum[war[glob[i].fi[2]]]++;
if(!oi)break;
}
if(oi)ret = 1;
if(oi)
{
// cout << "YES\n";
break;
}
}
while(next_permutation(glob.begin(), glob.end()));
return ret;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
m = M;
memset(d, -1, sizeof(d));
vector<int> ret(N, 0);
for(ll i = 1; i < N; i++)
{
v[P[i]].pb(i);
col[P[i]].pb(C[i]);
par[i] = P[i];
war[i] = C[i];
}
dfs(0, 0);
for(ll i = 0; i < N; i++)
{
ret[i] = cari(i);
// cout << i << " " << cari(i) << "\n";
}
// for(ll i = 0; i <)
// {
// vector<ll> tmp;
// for(auto a : v[0])
// {
// ada[a.se] = 1;
// tmp.pb(a.se);
// }
// sort(tmp.begin(), tmp.end());
// for(ll j = 1; j < tmp.size(); j++)
// if(tmp[j - 1] == tmp[j])
// ret[0] = 0;
// }
// vector<pair<ll, vector<ll> > > vv;
// for(ll i = 1; i < N; i++)
// if(v[i].size() == 0)
// ret[i] = 1;
// else
// {
// ret[i] = 1;
// vector<ll> tmp;
// for(auto a : v[i])
// tmp.pb(a.se);
// sort(tmp.begin(), tmp.end());
// for(ll j = 0; j < tmp.size(); j++)
// {
// if(!ada[tmp[j]])
// ret[0] = 0;
// }
// for(ll j = 1; j < tmp.size(); j++)
// if(tmp[j - 1] == tmp[j])
// {
// ret[0] = 0;
// ret[i] = 0;
// }
// vv.pb(mp((ll)tmp.size(), tmp));
// }
// sort(vv.begin(), vv.end());
return ret;
}
Compilation message
beechtree.cpp: In function 'll unik(std::vector<long long int>)':
beechtree.cpp:35:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(ll i = 1; i < X.size(); i++)
| ~~^~~~~~~~~~
beechtree.cpp: In function 'll cari(ll)':
beechtree.cpp:69:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::vector<long long int>, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(ll i = 0; i < glob.size(); i++)
| ~~^~~~~~~~~~~~~
beechtree.cpp:72:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::vector<long long int>, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(ll i = 0; i < glob.size(); i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
16988 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
17240 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16988 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
17240 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16988 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16988 KB |
Output is correct |
| 3 |
Execution timed out |
2045 ms |
16988 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
17240 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16988 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
16988 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
17240 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16988 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
16988 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
17240 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
16988 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
16988 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
16988 KB |
2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
