oj.uz

Submission #1068622

# Submission time Handle Problem Language Result Execution time Memory
1068622 2024-08-21T10:59:44 Z parsadox2 Beech Tree (IOI23_beechtree) C++17
5 / 100
 78 ms 42160 KB 
#include "beechtree.h"
#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;

const int N = 2e5 + 10;
int n , col[N] , m , sbt[N] , is_path[N] , cnt[N] , dis[N];
vector <int> adj[N];
vector <int> all , p;
bool bad[N] , mark[N];

void Dfs(int v)
{
    sbt[v] = 1;
    dis[v] = 0;
    for(auto u : adj[v])
    {
        Dfs(u);
        sbt[v] += sbt[u];
        bad[v] |= bad[u];
        dis[v] = max(dis[v] , dis[u] + 1);
    }
    if(adj[v].size() == 1)
    {
        int c = adj[v][0];
        if(sbt[c] == 1)
            is_path[v] = col[c];
        else if(col[c] == is_path[c])
            is_path[v] = col[c];
        else
            is_path[v] = -1;
    }
    else if(adj[v].size() > 1)
    {
        is_path[v] = -1;
    }
    vector <int> vec;
    for(auto u : adj[v])
        vec.push_back(col[u]);
    sort(vec.begin() , vec.end());
    for(int i = 1 ; i < vec.size() ; i++)  if(vec[i] == vec[i - 1])
        bad[v] = true;
}

void Dfs_all(int v)
{
    all.push_back(v);
    cnt[col[v]] = 0;
    for(auto u : adj[v])
        Dfs_all(u);
}

bool cmp(pair<int , int> aa , pair<int , int> bb)
{
    if(cnt[aa.F] != cnt[bb.F])
        return cnt[aa.F] < cnt[bb.F];
    return aa.F < bb.F;
}


bool Solve(int v)
{
    all.clear();
    Dfs_all(v);
    sort(all.begin() , all.end());
    vector <int> vec , all_col;
    int cnt_root = 0;
    vector <pair<int , int>> check;
    for(int i = 1 ; i < all.size() ; i++)
    {
        int now = all[i];
        all_col.push_back(col[now]);
        if(p[now] != 0)
        {
            cnt[col[now]]++;
            check.push_back(make_pair(col[now] , p[now]));
            mark[p[now]] = false;
        }
    }
    sort(all_col.begin() , all_col.end());
    all_col.resize(unique(all_col.begin() , all_col.end()) - all_col.begin());
    if(all_col.size() != adj[v].size())
        return false;
    sort(check.begin() , check.end() , cmp);
    int las = -1 , num = all_col.size() + 1;
    for(auto u : check)
    {
        if(u.F != las)
        {
            las = u.F;
            num--;
        }
        if((int)adj[u.S].size() < num)
            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];
    }
    Dfs(0);
    vector <int> res(n , 0);
    for(int i = 0 ; i < n ; i++)
    {
        if(is_path[i] != -1)
        {
            res[i] = true;
            continue;
        }
        if(bad[i] || dis[i] >= 3)
        {
            continue;
        }
        Solve(i);
    }
    return res;
}

Compilation message

beechtree.cpp: In function 'void Dfs(int)':
beechtree.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 1 ; i < vec.size() ; i++)  if(vec[i] == vec[i - 1])
      |                     ~~^~~~~~~~~~~~
beechtree.cpp: In function 'bool Solve(int)':
beechtree.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 1 ; i < all.size() ; i++)
      |                     ~~^~~~~~~~~~~~
beechtree.cpp:70:9: warning: unused variable 'cnt_root' [-Wunused-variable]
   70 |     int cnt_root = 0;
      |         ^~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Incorrect 2 ms 8540 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Incorrect 1 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 67 ms 42068 KB Output is correct
8 Correct 72 ms 42068 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 78 ms 42160 KB Output is correct
18 Correct 67 ms 41948 KB Output is correct
19 Correct 69 ms 42072 KB Output is correct
20 Correct 71 ms 42068 KB Output is correct

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 1 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Incorrect 2 ms 8540 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 1 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Incorrect 2 ms 8540 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 1 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Incorrect 2 ms 8540 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -