Submission #403576

#	Time	Username	Problem	Language	Result	Execution time	Memory
403576		maomao90	족보 (KOI18_family)	C++14	0 / 100	10 ms	15568 KiB

family

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

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

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