oj.uz

Submission #1068649

# Submission time Handle Problem Language Result Execution time Memory
1068649 2024-08-21T11:08:57 Z parsadox2 Beech Tree (IOI23_beechtree) C++17
22 / 100
 71 ms 42140 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)
{
    //cout << v << " : " << endl;
    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] != v)
        {
            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;
    all_col.clear();
    for(auto u : check)
        all_col.push_back(u.F);
    sort(all_col.begin() , all_col.end());
    all_col.resize(unique(all_col.begin() , all_col.end()) - all_col.begin());
    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--;
        }
        //cout << las << " " << num << " " << u.S << endl;
        if((int)adj[u.S].size() < num)
        {
            //cout << "WTF " << endl;
            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;
        }
        res[i] = 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:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 1 ; i < all.size() ; i++)
      |                     ~~^~~~~~~~~~~~
beechtree.cpp:71:9: warning: unused variable 'cnt_root' [-Wunused-variable]
   71 |     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 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct

Subtask #1
0.0 / 9.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 68 ms 42064 KB Output is correct
8 Correct 66 ms 42124 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 65 ms 42140 KB Output is correct
18 Correct 63 ms 42040 KB Output is correct
19 Correct 71 ms 42068 KB Output is correct
20 Correct 65 ms 42124 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 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 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct
13 Correct 2 ms 8628 KB Output is correct
14 Correct 2 ms 8652 KB Output is correct
15 Correct 57 ms 13996 KB Output is correct
16 Correct 39 ms 13736 KB Output is correct
17 Correct 40 ms 13732 KB Output is correct
18 Correct 54 ms 13736 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 68 ms 42064 KB Output is correct
6 Correct 66 ms 42124 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 64 ms 17488 KB Output is correct
12 Correct 70 ms 16976 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 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 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Incorrect 2 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 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 1 ms 8536 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Incorrect 2 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 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 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 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 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Incorrect 2 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 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 1 ms 8536 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Incorrect 2 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 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 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 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 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 1 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Incorrect 2 ms 8540 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -