| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403576 |
2021-05-13T09:41:06 Z |
maomao90 |
None (KOI18_family) |
C++14 |
|
10 ms |
15568 KB |
#include <bits/stdc++.h>
using namespace std;
#define mnto(x, y) x = min(x, (__typeof__(x)) y)
#define mxto(x, y) x = max(x, (__typeof__(x)) y)
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ii> vii;
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005
#define MAXL 20
int n[2], k;
vi adj[2][MAXN];
int p[2][MAXN], rt[2];
bool ans;
struct node {
int lo, hi, mid, val, lazy;
node *l, *r;
node(int lo, int hi): lo(lo), hi(hi), mid(lo + hi >> 1), val(0), lazy(-1) {
if (lo != hi) {
l = new node(lo, mid);
r = new node(mid + 1, hi);
}
}
void propo() {
if (lazy == -1) return;
val = lazy * (hi - lo + 1);
if (lo != hi) {
l -> lazy = lazy;
r -> lazy = lazy;
}
lazy = -1;
}
void update(int s, int e, int v) {
if (lo >= s && hi <= e) {
lazy = v;
propo();
return;
}
propo();
if (s <= mid) l -> update(s, e, v);
if (e > mid) r -> update(s, e, v);
l -> propo(); r -> propo();
val = l -> val + r -> val;
}
int sum(int s, int e) {
propo();
if (lo >= s && hi <= e) {
return val;
}
if (e <= mid) return l -> sum(s, e);
else if (s > mid) return r -> sum(s, e);
else return l -> sum(s, e) + r -> sum(s, e);
}
} *root;
int id[MAXN], pre;
ii leaves[2][MAXN];
ii dfs(int i, int u, int p) {
vii ranges;
for (int v : adj[i][u]) {
if (v == p) continue;
ii tmp = dfs(i, v, u);
if (!ans) return MP(-1, -1);
ranges.pb(tmp);
}
ii res;
if (ranges.empty()) {
if (id[u] == -1) id[u] = pre++;
res = MP(id[u], id[u]);
} else {
sort(ALL(ranges));
res = ranges[0];
REP (j, 1, ranges.size()) {
if (ranges[j].FI != res.SE + 1) {
ans = 0;
return MP(-1, -1);
}
res.SE = ranges[j].SE;
}
}
leaves[i][u] = res;
return res;
}
bool visited[MAXN];
void die(int i, int u, bool fi) {
if (visited[u]) return;
visited[u] = 1;
for (int v : adj[i][u]) {
if (p[i][u] == v) continue;
if (visited[v]) continue;
die(i, v, 0);
}
if (u <= k || fi) return;
if (root -> sum(leaves[i][u].FI, leaves[i][u].SE) != 0) {
ans = 0;
return;
}
}
map<ii, int> mp;
void search(int i, int u, int pp) {
bool leaf = 1;
for (int v : adj[i][u]) {
if (v == pp) continue;
leaf = 0;
search(i, v, u);
if (!ans) return;
}
if (leaf) return;
if (mp.find(leaves[i][u]) == mp.end()) {
root -> update(leaves[i][u].FI, leaves[i][u].SE, 1);
//printf("%d to %d\n", leaves[i][u].FI, leaves[i][u].SE);
} else {
//printf(" %d %d\n", u, mp[leaves[i][u]]);
die(1 - i, mp[leaves[i][u]], 1);
root -> update(leaves[i][u].FI, leaves[i][u].SE, 0);
}
}
bool equal(vi a, vi b) {
if (a.size() != b.size()) return 0;
REP (i, 0, a.size()) {
if (a[i] != b[i]) return 0;
}
return 1;
}
int main() {
scanf("%d%d%d", &n[0], &n[1], &k);
REP (i, 0, 2) {
REP (j, 1, n[i] + 1) {
scanf("%d", &p[i][j]);
if (p[i][j] == 0) rt[i] = j;
adj[i][p[i][j]].pb(j);
adj[i][j].pb(p[i][j]);
}
}
memset(id, -1, sizeof id);
ans = 1;
REP (i, 0, 2) {
dfs(i, rt[i], 0);
//printf("%d:\n", i);
//REP (j, 1, n[i] + 1) {
//printf(" %d: %d %d\n", j, leaves[i][j].FI, leaves[i][j].SE);
//}
}
if (!ans) {
printf("NO\n");
return 0;
}
REP (i, k + 1, n[1] + 1) {
mp[leaves[1][i]] = i;
//printf("%d %d: %d\n", leaves[1][i].FI, leaves[1][i].SE, i);
}
root = new node(0, k + 5);
search(0, rt[0], 0);
if (ans) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
/*
13 11 7
10 10 12 11 13 11 13 0 8 9 9 8 12
10 10 11 9 11 9 11 0 8 9 8
12 12 7
10 10 11 9 12 9 12 0 8 9 8 11
10 10 12 11 12 11 12 0 8 9 9 8
*/
Compilation message
family.cpp: In constructor 'node::node(int, int)':
family.cpp:36:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | node(int lo, int hi): lo(lo), hi(hi), mid(lo + hi >> 1), val(0), lazy(-1) {
| ~~~^~~~
family.cpp: In function 'ii dfs(int, int, int)':
family.cpp:6:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
91 | REP (j, 1, ranges.size()) {
| ~~~~~~~~~~~~~~~~~~~
family.cpp:91:7: note: in expansion of macro 'REP'
91 | REP (j, 1, ranges.size()) {
| ^~~
family.cpp: In function 'bool equal(vi, vi)':
family.cpp:6:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
142 | REP (i, 0, a.size()) {
| ~~~~~~~~~~~~~~
family.cpp:142:6: note: in expansion of macro 'REP'
142 | REP (i, 0, a.size()) {
| ^~~
family.cpp: In function 'int main()':
family.cpp:149:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d%d%d", &n[0], &n[1], &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:152:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d", &p[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15512 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15512 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15512 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15512 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15568 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
