# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1068962 | parsadox2 | Beech Tree (IOI23_beechtree) | C++17 | 2021 ms | 2097152 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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)
{
bool db = false;
if(aa == 3 && bb == 6)
db = true;
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;
if(flgb && all_deg[aa].size() < all_deg[bb].size())
return false;
if(flga && all_deg[bb].size() < all_deg[aa].size())
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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |