oj.uz

Submission #1068962

# Submission time Handle Problem Language Result Execution time Memory
1068962 2024-08-21T13:49:00 Z parsadox2 Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 2097152 KB 
#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)
{
    bool db = false;
    if(aa == 3 && bb == 6)
        db = true;
    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;
    if(flgb && all_deg[aa].size() < all_deg[bb].size())
        return false;
    if(flga && all_deg[bb].size() < all_deg[aa].size())
        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

beechtree.cpp: In function 'bool Check(int, int)':
beechtree.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 1 ; i < all_deg[aa].size() ; i++)  if(all_deg[aa][i - 1] < all_deg[aa][i])
      |                     ~~^~~~~~~~~~~~~~~~~~~~
beechtree.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 1 ; i < all_deg[bb].size() ; i++)  if(all_deg[bb][i - 1] < all_deg[bb][i])
      |                     ~~^~~~~~~~~~~~~~~~~~~~
beechtree.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   59 |     for(int i = 0 ; i < min(all_deg[aa].size() , all_deg[bb].size()) ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beechtree.cpp:51:10: warning: variable 'db' set but not used [-Wunused-but-set-variable]
   51 |     bool db = false;
      |          ^~
beechtree.cpp: In function 'bool Solve(int)':
beechtree.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     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:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int j = 1 ; j < all_col[i].size() ; j++)  if(all_col[i][j] == all_col[i][j - 1])
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14804 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14812 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 3 ms 14684 KB Output is correct
15 Correct 3 ms 14680 KB Output is correct
16 Correct 2 ms 14680 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Incorrect 3 ms 14776 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14804 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Runtime error 945 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14760 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 2 ms 14808 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 3 ms 14688 KB Output is correct
11 Correct 3 ms 14944 KB Output is correct
12 Correct 3 ms 14944 KB Output is correct
13 Correct 3 ms 14936 KB Output is correct
14 Correct 12 ms 14940 KB Output is correct
15 Correct 195 ms 27736 KB Output is correct
16 Correct 193 ms 26432 KB Output is correct
17 Correct 193 ms 27204 KB Output is correct
18 Execution timed out 2021 ms 26180 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14812 KB Output is correct
5 Runtime error 945 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14804 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 3 ms 14812 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14680 KB Output is correct
19 Correct 2 ms 14680 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 3 ms 14776 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14812 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 2 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Incorrect 3 ms 14776 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14804 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 3 ms 14812 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14680 KB Output is correct
19 Correct 2 ms 14680 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 3 ms 14776 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14812 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 3 ms 14680 KB Output is correct
12 Correct 2 ms 14680 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Incorrect 3 ms 14776 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 3 ms 14680 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14804 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 3 ms 14812 KB Output is correct
12 Correct 3 ms 14684 KB Output is correct
13 Correct 3 ms 14684 KB Output is correct
14 Correct 2 ms 14684 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14684 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 3 ms 14680 KB Output is correct
19 Correct 2 ms 14680 KB Output is correct
20 Correct 3 ms 14684 KB Output is correct
21 Incorrect 3 ms 14776 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
22 Halted 0 ms 0 KB -