oj.uz

Submission #403498

# Submission time Handle Problem Language Result Execution time Memory
403498 2021-05-13T08:45:51 Z maomao90 None (KOI18_family) C++14
0 / 100
 11 ms 15604 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) {
	for (int v : adj[i][u]) {
		if (v == pp) continue;
		if (v <= k) continue;
		search(i, v, u);
		if (!ans) return;
		if (mp.find(leaves[i][v]) == mp.end()) {
			root -> update(leaves[i][v].FI, leaves[i][v].SE, 1);
			//printf("%d to %d\n", leaves[i][v].FI, leaves[i][v].SE);
		} 
	}
	if (mp.find(leaves[i][u]) != mp.end()) {
		//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, 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:47: 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: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]
    6 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   91 |   REP (j, 1, ranges.size()) {
      |        ~~~~~~~~~~~~~~~~~~~              
family.cpp:91:3: note: in expansion of macro 'REP'
   91 |   REP (j, 1, ranges.size()) {
      |   ^~~
family.cpp: In function 'bool equal(vi, vi)':
family.cpp:6:40: 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++)
......
  141 |  REP (i, 0, a.size()) {
      |       ~~~~~~~~~~~~~~                    
family.cpp:141:2: note: in expansion of macro 'REP'
  141 |  REP (i, 0, a.size()) {
      |  ^~~
family.cpp: In function 'int main()':
family.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |  scanf("%d%d%d", &n[0], &n[1], &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
family.cpp:151:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |    scanf("%d", &p[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15544 KB Output is correct
3 Correct 9 ms 15540 KB Output is correct
4 Correct 9 ms 15536 KB Output is correct
5 Correct 9 ms 15564 KB Output is correct
6 Correct 9 ms 15536 KB Output is correct
7 Correct 9 ms 15600 KB Output is correct
8 Correct 9 ms 15532 KB Output is correct
9 Correct 11 ms 15564 KB Output is correct
10 Correct 9 ms 15564 KB Output is correct
11 Correct 10 ms 15540 KB Output is correct
12 Correct 10 ms 15588 KB Output is correct
13 Correct 11 ms 15564 KB Output is correct
14 Incorrect 9 ms 15604 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15544 KB Output is correct
3 Correct 9 ms 15540 KB Output is correct
4 Correct 9 ms 15536 KB Output is correct
5 Correct 9 ms 15564 KB Output is correct
6 Correct 9 ms 15536 KB Output is correct
7 Correct 9 ms 15600 KB Output is correct
8 Correct 9 ms 15532 KB Output is correct
9 Correct 11 ms 15564 KB Output is correct
10 Correct 9 ms 15564 KB Output is correct
11 Correct 10 ms 15540 KB Output is correct
12 Correct 10 ms 15588 KB Output is correct
13 Correct 11 ms 15564 KB Output is correct
14 Incorrect 9 ms 15604 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15544 KB Output is correct
3 Correct 9 ms 15540 KB Output is correct
4 Correct 9 ms 15536 KB Output is correct
5 Correct 9 ms 15564 KB Output is correct
6 Correct 9 ms 15536 KB Output is correct
7 Correct 9 ms 15600 KB Output is correct
8 Correct 9 ms 15532 KB Output is correct
9 Correct 11 ms 15564 KB Output is correct
10 Correct 9 ms 15564 KB Output is correct
11 Correct 10 ms 15540 KB Output is correct
12 Correct 10 ms 15588 KB Output is correct
13 Correct 11 ms 15564 KB Output is correct
14 Incorrect 9 ms 15604 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15564 KB Output is correct
2 Correct 9 ms 15544 KB Output is correct
3 Correct 9 ms 15540 KB Output is correct
4 Correct 9 ms 15536 KB Output is correct
5 Correct 9 ms 15564 KB Output is correct
6 Correct 9 ms 15536 KB Output is correct
7 Correct 9 ms 15600 KB Output is correct
8 Correct 9 ms 15532 KB Output is correct
9 Correct 11 ms 15564 KB Output is correct
10 Correct 9 ms 15564 KB Output is correct
11 Correct 10 ms 15540 KB Output is correct
12 Correct 10 ms 15588 KB Output is correct
13 Correct 11 ms 15564 KB Output is correct
14 Incorrect 9 ms 15604 KB Output isn't correct
15 Halted 0 ms 0 KB -