Submission #1068943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068943		parsadox2	Beech Tree (IOI23_beechtree)	C++17	0 / 100	2048 ms	2097152 KiB

beechtree

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

#define F first
#define S second

using namespace std;

const int N = 2e5 + 10;

int n , m , col[N];
vector <int> p , adj[N] , all_col[N] , all_deg[N];
bool bad[N] , marked[N];
vector <int> all;

void Dfs(int v)
{
    all.push_back(v);
    for(auto u : adj[v])
    {
        all_deg[u] = all_deg[v];
        all_deg[u].push_back(adj[v].size());
        Dfs(u);
    }
}

bool cmp(vector <int> aa , vector <int> bb)
{
    return aa.size() > bb.size();
}

bool Sub_seq(vector <int> aa , vector <int> bb)
{
    if(aa.size() > bb.size())
        swap(aa , bb);
    for(auto u : aa)
        marked[u] = true;
    for(auto u : bb)
        marked[u] = false;
    bool flg = true;
    for(auto u : aa)  if(marked[u])
    {
        marked[u] = false;
        flg = false;
    }
    return flg;
}

bool Check(int aa , int bb)
{
    for(int i = 1 ; i < all_deg[aa].size() ; i++)  if(all_deg[aa][i - 1] < all_deg[aa][i])
        return false;
    for(int i = 1 ; i < all_deg[bb].size() ; i++)  if(all_deg[bb][i - 1] < all_deg[bb][i])
        return false;
    bool flga = false , flgb = false;
    for(int i = 0 ; i < min(all_deg[aa].size() , all_deg[bb].size()) ; i++)
    {
        if(all_deg[aa][i] < all_deg[bb][i])
            flga = true;
        if(all_deg[bb][i] < all_deg[aa][i])
            flgb = true;
    }
    if(flga && flgb)
        return false;
    return true;
}

bool Solve(int v)
{
    all_deg[v].clear();
    all.clear();
    Dfs(v);
    for(auto u : all)  if(bad[u])
        return false;
    vector <vector<int>> vec;
    for(auto u : all)
        vec.push_back(all_col[u]);
    sort(vec.begin() , vec.end() , cmp);
    for(int i = 1 ; i < all.size() ; i++)  if(!Sub_seq(vec[i] , vec[i - 1]))
        return false;
    for(auto x : all)  for(auto y : all)  if(!Check(x , y))
        return false;
    return true;
}

vector<int> beechtree(int nn, int mm, vector<int> P, vector<int> C)
{
    n = nn;  
    m = mm;
    p = P;
    for(int i = 1 ; i < n ; i++)
    {
        adj[P[i]].push_back(i);
        col[i] = C[i];
    }
    for(int i = 0 ; i < n ; i++)
    {
        for(auto u : adj[i])
            all_col[i].push_back(col[u]);
        sort(all_col[i].begin() , all_col[i].end());
        for(int j = 1 ; j < all_col[i].size() ; j++)  if(all_col[i][j] == all_col[i][j - 1])
            bad[i] = true;
    }
    vector <int> res;
    for(int i = 0 ; i < n ; i++)
        res.push_back(Solve(i));
    return res;
}

Compilation message (stderr)

beechtree.cpp: In function 'bool Check(int, int)':
beechtree.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 1 ; i < all_deg[aa].size() ; i++)  if(all_deg[aa][i - 1] < all_deg[aa][i])
      |                     ~~^~~~~~~~~~~~~~~~~~~~
beechtree.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 1 ; i < all_deg[bb].size() ; i++)  if(all_deg[bb][i - 1] < all_deg[bb][i])
      |                     ~~^~~~~~~~~~~~~~~~~~~~
beechtree.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   56 |     for(int i = 0 ; i < min(all_deg[aa].size() , all_deg[bb].size()) ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beechtree.cpp: In function 'bool Solve(int)':
beechtree.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 1 ; i < all.size() ; i++)  if(!Sub_seq(vec[i] , vec[i - 1]))
      |                     ~~^~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j = 1 ; j < all_col[i].size() ; j++)  if(all_col[i][j] == all_col[i][j - 1])
      |                         ~~^~~~~~~~~~~~~~~~~~~

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