oj.uz

Submission #912676

# Submission time Handle Problem Language Result Execution time Memory
912676 2024-01-19T17:55:39 Z Ludissey Beech Tree (IOI23_beechtree) C++17
0 / 100
 1 ms 348 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
int N,M;
vector<vector<int>> child;
vector<int> C;
vector<int> P;
vector<int> outp;


std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
    N=n; M=m;
    C.assign(c.begin(), c.end());
    P.assign(p.begin(), p.end());
    child.resize(n);
    outp.resize(n,0);
    P[0]=0;
    vector<int> depth(N,0);
    vector<bool> triple(N,false);
    for (int i = 1; i < N; i++) child[P[i]].push_back(i);
    for (int i = 1; i < N; i++) {
        if(P[P[P[i]]]!=P[P[i]]) triple[P[P[P[i]]]]=true;
    }

    for (int i = 0; i < n; i++)
    {
        if(child[i].size()>2||triple[i]) continue;
        else if(child[i].size()==0) outp[i]=1;
        else if(child[i].size()==2) {
            unordered_set<int> childColor;
            for (auto u : child[i]) childColor.insert(c[u]);
            unordered_set<int> child1Color;
            unordered_set<int> child2Color;
            if(triple[i]||childColor.size()!=2||(child[child[i][0]].size()+child[child[i][1]].size())>2) continue;
            for (auto u : child[child[i][0]])
            {
                child1Color.insert(c[u]);
                childColor.insert(c[u]);
            }
            if(child1Color.size()!=child[child[i][0]].size()) continue;
            for (auto u : child[child[i][1]])
            {
                child1Color.insert(c[u]);
                child2Color.insert(c[u]);
                childColor.insert(c[u]);
            }
            if(child2Color.size()!=child[child[i][1]].size()) continue;
            if(child1Color.size()!=child[child[i][0]].size()+child[child[i][1]].size()) continue;
            if(childColor.size()!=2) continue;
            outp[i]=1;
            if(i==0) outp[0]=0;
        }else{
            if(triple[i]) continue;
            outp[i]=1;
            int u=i;
            int l=c[u];
            while(child[u].size()>0){
                if(child[u].size()!=1||l!=c[u]) { outp[i]=0; break; }
                u=child[u][0];
                l=c[u];
            }
        }
    }
    return {outp};
}

Subtask #0
0.0 / 0.0

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

Subtask #2
0.0 / 5.0

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

Subtask #3
0.0 / 9.0

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

Subtask #5
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #9
0.0 / 12.0

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