| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1024746 | 2024-07-16T09:54:08 Z | LIF | Beech Tree (IOI23_beechtree) | C++17 | 97 ms | 43580 KB |
#include "beechtree.h"
#include<bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
vector<int> vv[500005];
int maxdepth[500005];
int depth[500005];
int ans[500005];
void dfs(int now,int dep)
{
maxdepth[now] = depth[now] = dep;
for(auto it : vv[now])
{
dfs(it,dep+1);
maxdepth[now] = max(maxdepth[now],maxdepth[it]);
}
return;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
for(int i=1;i<P.size();i++)
{
int father = P[i];
int son = i;
vv[father].push_back(son);
}
dfs(0,1);
// ???憭???暺?
for(int i=0;i<N;i++)
{
if(maxdepth[i] == depth[i])ans[i] = 1;
else
{
if(maxdepth[i] == depth[i] + 1)
{
map<int,int> mp;
bool flag = true;
for(auto it : vv[i])
{
int nowcolor = C[it];
if(mp[nowcolor] != 0)
{
flag = false;
break;
}
else mp[nowcolor] = 1;
}
if(flag == true)ans[i] = 1;
else ans[i] = 0;
}
else
{
if(maxdepth[i] == depth[i] + 2)
{
map<int,int> mp;
bool flag = true;
for(auto it : vv[i]) //擐?靽??????脤???詨?嚗?
{
int nowcolor = C[it];
if(mp[nowcolor] != 0)
{
flag = false;
break;
}
else mp[nowcolor] = 1;
}
int cnt = 0;
for(auto it : vv[i])
{
if(vv[it].size() >= 1)
{
cnt++;
map<int,int> mp2;
for(auto j : vv[it])
{
int nowcolor = C[j];
if(mp2[nowcolor] != 0)
{
flag = false;
break;
}
else mp2[nowcolor] = 1;
if(mp[nowcolor] == 0)flag = false;
}
}
}
if(cnt >= 2)flag = false;
if(flag == true)ans[i] = 1;
else ans[i] = 0;
}
else ans[i] = 0;
}
}
}
vector<int> temp;
for(int i=0;i<N;i++)
{
temp.push_back(ans[i]);
}
/* for(int i=0;i<100;i++)if(ans[i] == 0)cout<<i<<endl;
cout<<maxdepth[49]<<" "<<depth[49]<<" "<<ans[49]<<endl;
for(auto it : vv[49])
{
cout<<it<<" "<<vv[it].size()<<" "<<C[it]<<" "<<endl;
cout<<"son"<<endl;
if(vv[it].size() == 2)cout<<vv[it][0]<<" "<<C[vv[it][0]]<<endl;
if(vv[it].size() == 2)cout<<vv[it][1]<<" "<<C[vv[it][1]]<<endl;
cout<<endl;
}
*/
return temp;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 17756 KB | Output is correct |
| 2 | Incorrect | 3 ms | 17880 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 | 2 ms | 17756 KB | Output is correct |
| 2 | Correct | 3 ms | 17756 KB | Output is correct |
| 3 | Incorrect | 3 ms | 17752 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 17756 KB | Output is correct |
| 2 | Correct | 3 ms | 17756 KB | Output is correct |
| 3 | Incorrect | 3 ms | 17752 KB | 2nd lines differ - on the 1st token, expected: '1', found: '0' |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 17756 KB | Output is correct |
| 2 | Correct | 3 ms | 17756 KB | Output is correct |
| 3 | Correct | 3 ms | 17756 KB | Output is correct |
| 4 | Correct | 3 ms | 17756 KB | Output is correct |
| 5 | Correct | 3 ms | 17756 KB | Output is correct |
| 6 | Correct | 3 ms | 17756 KB | Output is correct |
| 7 | Correct | 3 ms | 17756 KB | Output is correct |
| 8 | Correct | 3 ms | 17756 KB | Output is correct |
| 9 | Incorrect | 3 ms | 17864 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 | 2 ms | 17756 KB | Output is correct |
| 2 | Correct | 3 ms | 17756 KB | Output is correct |
| 3 | Correct | 3 ms | 17756 KB | Output is correct |
| 4 | Correct | 3 ms | 17756 KB | Output is correct |
| 5 | Correct | 59 ms | 43580 KB | Output is correct |
| 6 | Correct | 59 ms | 43464 KB | Output is correct |
| 7 | Correct | 3 ms | 17876 KB | Output is correct |
| 8 | Correct | 3 ms | 17756 KB | Output is correct |
| 9 | Correct | 3 ms | 17916 KB | Output is correct |
| 10 | Correct | 3 ms | 17888 KB | Output is correct |
| 11 | Correct | 61 ms | 27632 KB | Output is correct |
| 12 | Correct | 97 ms | 25676 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 17756 KB | Output is correct |
| 2 | Incorrect | 3 ms | 17880 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 | 2 ms | 17756 KB | Output is correct |
| 2 | Correct | 3 ms | 17756 KB | Output is correct |
| 3 | Correct | 3 ms | 17756 KB | Output is correct |
| 4 | Correct | 3 ms | 17756 KB | Output is correct |
| 5 | Correct | 3 ms | 17752 KB | Output is correct |
| 6 | Correct | 3 ms | 17756 KB | Output is correct |
| 7 | Correct | 3 ms | 17756 KB | Output is correct |
| 8 | Correct | 3 ms | 17756 KB | Output is correct |
| 9 | Correct | 3 ms | 17756 KB | Output is correct |
| 10 | Correct | 3 ms | 17864 KB | Output is correct |
| 11 | Correct | 3 ms | 17756 KB | Output is correct |
| 12 | Correct | 3 ms | 17756 KB | Output is correct |
| 13 | Correct | 3 ms | 17756 KB | Output is correct |
| 14 | Correct | 3 ms | 17756 KB | Output is correct |
| 15 | Correct | 3 ms | 17756 KB | Output is correct |
| 16 | Incorrect | 3 ms | 17756 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 | 3 ms | 17756 KB | Output is correct |
| 2 | Incorrect | 3 ms | 17880 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 | 2 ms | 17756 KB | Output is correct |
| 2 | Correct | 3 ms | 17756 KB | Output is correct |
| 3 | Correct | 3 ms | 17756 KB | Output is correct |
| 4 | Correct | 3 ms | 17756 KB | Output is correct |
| 5 | Correct | 3 ms | 17752 KB | Output is correct |
| 6 | Correct | 3 ms | 17756 KB | Output is correct |
| 7 | Correct | 3 ms | 17756 KB | Output is correct |
| 8 | Correct | 3 ms | 17756 KB | Output is correct |
| 9 | Correct | 3 ms | 17756 KB | Output is correct |
| 10 | Correct | 3 ms | 17864 KB | Output is correct |
| 11 | Correct | 3 ms | 17756 KB | Output is correct |
| 12 | Correct | 3 ms | 17756 KB | Output is correct |
| 13 | Correct | 3 ms | 17756 KB | Output is correct |
| 14 | Correct | 3 ms | 17756 KB | Output is correct |
| 15 | Correct | 3 ms | 17756 KB | Output is correct |
| 16 | Incorrect | 3 ms | 17756 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 | 3 ms | 17756 KB | Output is correct |
| 2 | Incorrect | 3 ms | 17880 KB | 2nd lines differ - on the 2nd token, expected: '1', found: '0' |
| 3 | Halted | 0 ms | 0 KB | - |