oj.uz

Submission #1068943

# Submission time Handle Problem Language Result Execution time Memory
1068943 2024-08-21T13:39:07 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)
{
    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

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 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 5 ms 14428 KB Output is correct
4 Correct 5 ms 14428 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 5 ms 14384 KB Output is correct
7 Runtime error 1216 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 4 ms 14688 KB Output is correct
2 Correct 4 ms 14684 KB Output is correct
3 Correct 2 ms 14932 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 2 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 14940 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 10 ms 15052 KB Output is correct
15 Correct 198 ms 25344 KB Output is correct
16 Correct 174 ms 26432 KB Output is correct
17 Correct 175 ms 25932 KB Output is correct
18 Execution timed out 2048 ms 25156 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 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 4 ms 14684 KB Output is correct
5 Runtime error 1216 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 5 ms 14428 KB Output is correct
3 Incorrect 5 ms 14428 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 4 ms 14684 KB Output is correct
5 Incorrect 5 ms 14428 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 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 5 ms 14428 KB Output is correct
3 Incorrect 5 ms 14428 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 4 ms 14684 KB Output is correct
5 Incorrect 5 ms 14428 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 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 5 ms 14428 KB Output is correct
3 Incorrect 5 ms 14428 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -