| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 403568 |
2021-05-13T09:37:48 Z |
maomao90 |
None (KOI18_family) |
C++14 |
|
18 ms |
29656 KB |
#include <bits/stdc++.h>
using namespace std;
bool main1();
#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);
}
}
int main() {
scanf("%d%d%d", &n[0], &n[1], &k);
//n[0] = 8, n[1] = 8, k = 4;
//srand(time(0));
//REP (i, 1, k + 1) {
//p[0][i] = rand() % (n[0] - k) + k + 1;
//p[1][i] = rand() % (n[1] - k) + k + 1;
//}
//REP (i, k + 1, n[0]) {
//p[0][i] = rand() % (n[0] - i) + i + 1;
//}
//REP (i, k + 1, n[1]) {
//p[1][i] = rand() % (n[1] - i) + i + 1;
//}
//p[0][n[0]] = 0;
//p[1][n[1]] = 0;
//REP (i, 0, 2) {
//REP (j, 1, n[i] + 1) {
//printf("%d ", p[i][j]);
//}
//printf("\n");
//}
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");
}
//if (ans == main1()) {
//printf("YES\n");
//} else {
//printf("NO\n");
//}
//if (ans) {
//printf("YES\n");
//} else {
//printf("NO\n");
//}
return 0;
}
int l[2][MAXN];
vi _leaves[2][MAXN];
vi _dfs(int id, int u, int p) {
vi res;
for (int v : adj[id][u]) {
if (v == p) continue;
vi tmp = _dfs(id, v, u);
for (int i : tmp) {
res.pb(i);
}
}
if (res.empty()) res.pb(u);
_leaves[id][u] = res;
return res;
}
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;
}
bool main1() {
REP (i, 0, 2) {
_dfs(i, rt[i], 0);
REP (j, 1, n[i] + 1) {
sort(ALL(_leaves[i][j]));
}
}
int _cnt = 0;
REP (i, 1, n[1] + 1) {
bool found = 0;
REP (j, 1, n[0] + 1) {
if (equal(_leaves[1][i], _leaves[0][j])) {
found = 1;
}
}
if (found) _cnt++;
}
return _cnt == n[1];
}
/*
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
8 8 5
8 6 6 6 7 8 8 0
8 8 6 6 7 8 8 0
8 8 5
8 7 6 6 6 8 8 0
8 6 6 6 7 8 8 0
*/
Compilation message
family.cpp: In constructor 'node::node(int, int)':
family.cpp:38:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | 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:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
93 | REP (j, 1, ranges.size()) {
| ~~~~~~~~~~~~~~~~~~~
family.cpp:93:3: note: in expansion of macro 'REP'
93 | REP (j, 1, ranges.size()) {
| ^~~
family.cpp: In function 'bool equal(vi, vi)':
family.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
227 | REP (i, 0, a.size()) {
| ~~~~~~~~~~~~~~
family.cpp:227:2: note: in expansion of macro 'REP'
227 | REP (i, 0, a.size()) {
| ^~~
family.cpp: In function 'int main()':
family.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%d%d%d", &n[0], &n[1], &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:165:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%d", &p[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
29656 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
29600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
29656 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
29600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
29656 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
29600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
29656 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
29600 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
