Submission #65660

#	Time	Username	Problem	Language	Result	Execution time	Memory
65660		imeimi2000	족보 (KOI18_family)	C++17	100 / 100	783 ms	83844 KiB

family

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m, k;
vector<int> child1[300001];
vector<int> child2[300001];
int st[300001];
int ed[300001];
int rev[300001];
int par[300001][20];
int dep[300001];

void fail(int i) {
    printf("NO\n");
    exit(0);
}

void dfs(int x) {
    static int ord = 1;
    rev[st[x] = ord] = x;
    for (int i : child1[x]) {
        par[i][0] = x;
        dep[i] = dep[x] + 1;
        dfs(i);
    }
    if (child1[x].empty()) ++ord;
    ed[x] = ord - 1;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; i--; ) {
        if ((dep[x] - dep[y]) >> i) x = par[x][i];
    }
    if (x == y) return x;
    for (int i = 20; i--; ) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}

int anc(int x, int c) {
    for (int i = 20; i--; ) {
        if ((c >> i) & 1) x = par[x][i];
    }
    return x;
}

int segn[1 << 20];
int segx[1 << 20];

void update(int seg[], int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i] = v;
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(seg, i << 1, s, m, x, v);
    else update(seg, i << 1 | 1, m + 1, e, x, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

const int inf = 1e7;
int query(int seg[], int i, int s, int e, int x, int y) {
    if (e < x || y < s) return -inf;
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(query(seg, i << 1, s, m, x, y), 
               query(seg, i << 1 | 1, m + 1, e, x, y));
}

int big[300001];
int s2[300001];
int e2[300001];
void dfs2(int x) {
    static int ord = 1;
    s2[x] = ord;
    if (child2[x].empty()) {
        big[x] = x;
        update(segx, 1, 1, k, ord, st[x]);
        update(segn, 1, 1, k, ord, k - st[x]);
        e2[x] = ord;
        ++ord;
        return;
    }
    int p = -1;
    for (int i : child2[x]) {
        dfs2(i);
        if (p != -1) p = lca(p, big[i]);
        else p = big[i];
    }
    e2[x] = ord - 1;
    vector<pii> as;
    for (int i : child2[x]) {
        if (p != big[i]) {
            int t = anc(big[i], dep[big[i]] - dep[p] - 1);
            as.emplace_back(t, i);
        }
    }
    sort(as.begin(), as.end());
    int mn = k, mx = 0, sum = 0;
    for (int it = 0; it < as.size(); ++it) {
        int t, y;
        tie(t, y) = as[it];
        if (it && as[it - 1].first != t) {
            int t = as[it - 1].first;
            if (mn != st[t]) fail(0);
            if (mx != ed[t]) fail(1);
            if (mx - mn + 1 != sum) fail(2);
            mn = k;
            mx = 0;
            sum = 0;
        }
        mn = min(mn, k - query(segn, 1, 1, k, s2[y], e2[y]));
        mx = max(mx, query(segx, 1, 1, k, s2[y], e2[y]));
        sum += e2[y] - s2[y] + 1;
    }
    
    if (as.size()) {
        int t = as[as.size() - 1].first;
        if (mn != st[t]) fail(0);
        if (mx != ed[t]) fail(1);
        if (mx - mn + 1 != sum) fail(2);
    }
    
    big[x] = p;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) {
        int p;
        cin >> p;
        child1[p].push_back(i);
	}
	for (int i = 1; i <= m; ++i) {
        int p;
        cin >> p;
        child2[p].push_back(i);
	}
	dfs(child1[0][0]);
	for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
	}
	dfs2(child2[0][0]);
	printf("YES\n");
	return 0;
}

Compilation message (stderr)

family.cpp: In function 'void dfs2(int)':
family.cpp:122:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int it = 0; it < as.size(); ++it) {
                      ~~~^~~~~~~~~~~

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