Submission #403568

#	Time	Username	Problem	Language	Result	Execution time	Memory
403568		maomao90	족보 (KOI18_family)	C++14	0 / 100	18 ms	29656 KiB

family

#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 (stderr)

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]);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41