# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|
403461 | | lyc | 족보 (KOI18_family) | C++14 | | 3099 ms | 196892 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
//const int mxN = 3e5+5;
//const int mxK = 3e5+5;
const int mxN = 5005;
const int mxK = 5005;
int K;
struct Tree {
int N;
vector<int> g[mxN];
int pa[mxN][14];
int _lca[mxK][mxK];
int dep[mxN];
void read() {
FOR(i,1,N){
int P; cin >> P;
g[P].push_back(i);
}
}
void dfs(int u) {
FOR(k,1,13) pa[u][k] = (pa[u][k-1] == -1 ? -1 : pa[pa[u][k-1]][k-1]);
for (int& v : g[u]) {
pa[v][0] = u;
dep[v] = dep[u]+1;
dfs(v);
}
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a,b);
RFOR(k,13,0) if (pa[a][k] != -1 && dep[pa[a][k]] >= dep[b]) {
a = pa[a][k];
}
if (a == b) return a;
RFOR(k,13,0) if (pa[a][k] != pa[b][k]) {
a = pa[a][k], b = pa[b][k];
}
return pa[a][0];
}
void run() {
memset(pa,-1,sizeof pa);
dep[0] = 0;
dfs(0);
FOR(i,1,N){
FOR(j,i+1,N){
_lca[i][j] = _lca[j][i] = dep[lca(i,j)];
}
}
}
int cmp(int i, int j, int k) {
if (_lca[i][j] == _lca[j][k]) return 0;
return _lca[i][j] < _lca[j][k] ? -1 : 1;
}
} A, B;
bool chk(int i, int j, int k) {
int x = A.cmp(i,j,k), y = B.cmp(i,j,k);
if (x == 0 || y == 0) return 0;
return ((x < 0) ^ (y < 0));
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> A.N >> B.N >> K;
A.read();
B.read();
A.run();
B.run();
bool die = 0;
FOR(i,1,K){
FOR(j,i+1,K){
FOR(k,j+1,K){
die |= chk(i,j,k);
die |= chk(i,k,j);
die |= chk(j,i,k);
}
}
}
cout << (die ? "NO" : "YES") << '\n';
}
# | 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... |