| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 846848 | 2023-09-08T14:21:08 Z | ogkostya | Beech Tree (IOI23_beechtree) | C++17 | 78 ms | 13256 KB |
#include "beechtree.h"
#include <algorithm>
#include <queue>
#include <set>
#include <utility>
int cn[200010];
int lev[200010];
std::vector<int> down[200010];
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
std::vector<int> ans{ };
bool sub2 = true;
for (int i = 1; sub2 && i < N; i++)
{
sub2 &= P[i] == i - 1;
}
if (sub2)
{
ans.push_back(1);
ans.push_back(1);
for (int i = N - 3; i >= 0; i--)
{
sub2 &= C[i + 1] == C[N - 1];
ans.push_back(sub2 ? 1 : 0);
}
std::reverse(ans.begin(), ans.end());
return ans;
}
// sub 4
std::fill_n(cn, M + 1, 0);
bool sub4 = true;
for (size_t i = 0; i < C.size(); i++)
{
if (++cn[C[i]] > 2)
{
sub4 = false;
break;
}
}
for (int i = 1; i < N; i++)
{
down[P[i]].push_back(i);
}
std::queue<int> q = {};
std::fill_n(lev, N + 1, 0);
std::fill_n(cn, N + 1, 0);
for (int i = 0; i < N; i++)
{
cn[i] = down[i].size();
if (down[i].size() == 0)
{
q.push(i);
}
}
while (q.size() > 0)
{
int ii = q.front();
q.pop();
if (ii == 0)
break;
if (--cn[P[ii]] == 0)
{
q.push(P[ii]);
lev[P[ii]] = 1 + lev[ii];
}
}
for (int i = 0; i < N; i++)
{
if (i == 0 && !sub4 && lev[i] == 2)
{
std::set<int> s = {};
bool ok = true;
std::vector<std::pair<int, int>> sort = {};
for (size_t j = 0; j < down[0].size(); j++)
{
if (s.count(C[down[0][j]]) == 0)
{
s.insert(C[down[0][j]]);
sort.push_back(std::make_pair(down[down[0][j]].size(), down[0][j]));
}
else
{
ok = false;
break;
}
}
if (ok)
{
std::sort(sort.begin(), sort.end());
std::reverse(sort.begin(), sort.end());
for (size_t k = 0; ok && i < sort.size(); k++)
{
std::set<int> next = {};
int index = sort[k].second;
for (size_t j = 0; j < down[index].size(); j++)
{
if (s.count(C[down[index][j]]) == 1 && next.count(C[down[index][j]]) == 0)
{
next.insert(C[down[index][j]]);
}
else
{
ok = false;
break;
}
}
s = next;
}
}
ans.push_back(ok ? 1 : 0);
}
else if (lev[i] == 0)
{
ans.push_back(1);
}
else if (lev[i] == 1)
{
std::set<int> s = {};
bool ok = true;
for (size_t j = 0; j < down[i].size(); j++)
{
if (s.count(C[down[i][j]]) == 0)
{
s.insert(C[down[i][j]]);
}
else
{
ok = false;
break;
}
}
ans.push_back(ok ? 1 : 0);
}
else if (lev[i] == 2)
{
std::set<int> s = {};
bool ok = true;
int f = -1;
for (size_t j = 0; j < down[i].size(); j++)
{
if (down[down[i][j]].size() > 0)
{
if (f == -1)
{
f = down[i][j];
}
else
{
ok = false;
break;
}
}
if (s.count(C[down[i][j]]) == 0)
{
s.insert(C[down[i][j]]);
}
else
{
ok = false;
break;
}
}
if (ok)
{
for (size_t j = 0; j < down[f].size(); j++)
{
if (s.count(C[down[f][j]]) == 1)
{
s.erase(C[down[f][j]]);
}
else
{
ok = false;
break;
}
}
}
ans.push_back(ok ? 1 : 0);
}
else
{
ans.push_back(0);
}
}
return ans;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Correct | 1 ms | 5468 KB | Output is correct |
| 3 | Correct | 1 ms | 5468 KB | Output is correct |
| 4 | Correct | 1 ms | 5468 KB | Output is correct |
| 5 | Correct | 1 ms | 5468 KB | Output is correct |
| 6 | Correct | 1 ms | 5468 KB | Output is correct |
| 7 | Correct | 2 ms | 5468 KB | Output is correct |
| 8 | Correct | 1 ms | 5464 KB | Output is correct |
| 9 | Correct | 2 ms | 5464 KB | Output is correct |
| 10 | Correct | 1 ms | 5468 KB | Output is correct |
| 11 | Correct | 2 ms | 5464 KB | Output is correct |
| 12 | Correct | 1 ms | 5468 KB | Output is correct |
| 13 | Correct | 1 ms | 5468 KB | Output is correct |
| 14 | Correct | 1 ms | 5720 KB | Output is correct |
| 15 | Correct | 1 ms | 5464 KB | Output is correct |
| 16 | Correct | 2 ms | 5464 KB | Output is correct |
| 17 | Correct | 1 ms | 5468 KB | Output is correct |
| 18 | Correct | 1 ms | 5468 KB | Output is correct |
| 19 | Correct | 1 ms | 5468 KB | Output is correct |
| 20 | Incorrect | 3 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 21 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Correct | 1 ms | 5468 KB | Output is correct |
| 3 | Correct | 1 ms | 5468 KB | Output is correct |
| 4 | Correct | 1 ms | 5468 KB | Output is correct |
| 5 | Correct | 1 ms | 5468 KB | Output is correct |
| 6 | Correct | 1 ms | 5468 KB | Output is correct |
| 7 | Correct | 47 ms | 9672 KB | Output is correct |
| 8 | Correct | 47 ms | 9684 KB | Output is correct |
| 9 | Correct | 1 ms | 5464 KB | Output is correct |
| 10 | Correct | 1 ms | 5468 KB | Output is correct |
| 11 | Correct | 1 ms | 5464 KB | Output is correct |
| 12 | Correct | 1 ms | 5468 KB | Output is correct |
| 13 | Correct | 2 ms | 5468 KB | Output is correct |
| 14 | Correct | 2 ms | 5468 KB | Output is correct |
| 15 | Correct | 2 ms | 5468 KB | Output is correct |
| 16 | Correct | 2 ms | 5468 KB | Output is correct |
| 17 | Correct | 45 ms | 9684 KB | Output is correct |
| 18 | Correct | 53 ms | 9792 KB | Output is correct |
| 19 | Correct | 46 ms | 9676 KB | Output is correct |
| 20 | Correct | 46 ms | 9676 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 5464 KB | Output is correct |
| 2 | Correct | 1 ms | 5468 KB | Output is correct |
| 3 | Correct | 1 ms | 5468 KB | Output is correct |
| 4 | Correct | 1 ms | 5468 KB | Output is correct |
| 5 | Correct | 1 ms | 5468 KB | Output is correct |
| 6 | Correct | 1 ms | 5468 KB | Output is correct |
| 7 | Correct | 1 ms | 5468 KB | Output is correct |
| 8 | Correct | 1 ms | 5468 KB | Output is correct |
| 9 | Incorrect | 2 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 10 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Correct | 1 ms | 5468 KB | Output is correct |
| 3 | Correct | 2 ms | 5468 KB | Output is correct |
| 4 | Correct | 1 ms | 5464 KB | Output is correct |
| 5 | Correct | 47 ms | 9672 KB | Output is correct |
| 6 | Correct | 47 ms | 9684 KB | Output is correct |
| 7 | Correct | 1 ms | 5464 KB | Output is correct |
| 8 | Correct | 2 ms | 5464 KB | Output is correct |
| 9 | Correct | 2 ms | 6236 KB | Output is correct |
| 10 | Correct | 3 ms | 6236 KB | Output is correct |
| 11 | Correct | 68 ms | 13256 KB | Output is correct |
| 12 | Correct | 78 ms | 12112 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Correct | 1 ms | 5468 KB | Output is correct |
| 3 | Correct | 2 ms | 5468 KB | Output is correct |
| 4 | Correct | 1 ms | 5464 KB | Output is correct |
| 5 | Correct | 2 ms | 5464 KB | Output is correct |
| 6 | Correct | 1 ms | 5468 KB | Output is correct |
| 7 | Correct | 2 ms | 5464 KB | Output is correct |
| 8 | Correct | 1 ms | 5468 KB | Output is correct |
| 9 | Correct | 1 ms | 5468 KB | Output is correct |
| 10 | Correct | 1 ms | 5720 KB | Output is correct |
| 11 | Correct | 1 ms | 5464 KB | Output is correct |
| 12 | Correct | 2 ms | 5464 KB | Output is correct |
| 13 | Correct | 1 ms | 5468 KB | Output is correct |
| 14 | Correct | 1 ms | 5468 KB | Output is correct |
| 15 | Correct | 1 ms | 5468 KB | Output is correct |
| 16 | Incorrect | 3 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 17 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Correct | 1 ms | 5468 KB | Output is correct |
| 3 | Correct | 2 ms | 5468 KB | Output is correct |
| 4 | Correct | 1 ms | 5464 KB | Output is correct |
| 5 | Correct | 2 ms | 5464 KB | Output is correct |
| 6 | Correct | 1 ms | 5468 KB | Output is correct |
| 7 | Correct | 2 ms | 5464 KB | Output is correct |
| 8 | Correct | 1 ms | 5468 KB | Output is correct |
| 9 | Correct | 1 ms | 5468 KB | Output is correct |
| 10 | Correct | 1 ms | 5720 KB | Output is correct |
| 11 | Correct | 1 ms | 5464 KB | Output is correct |
| 12 | Correct | 2 ms | 5464 KB | Output is correct |
| 13 | Correct | 1 ms | 5468 KB | Output is correct |
| 14 | Correct | 1 ms | 5468 KB | Output is correct |
| 15 | Correct | 1 ms | 5468 KB | Output is correct |
| 16 | Incorrect | 3 ms | 5468 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 17 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 5468 KB | Output is correct |
| 2 | Incorrect | 1 ms | 5468 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |