답안 #914304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914304	2024-01-21T15:03:53 Z	marvinthang	참나무 (IOI23_beechtree)	C++17	9 / 100	80 ms	26812 KB

beechtree

/*************************************
*    author: marvinthang             *
*    created: 21.01.2024 19:34:55    *
*************************************/
 
#include "beechtree.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif
 
template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
 
// end of template
 
vector <int> beechtree(int N, int M, vector <int> P, vector <int> C) {
    vector <set <pair <int, int>>> order(N);
    vector <int> sz(N, 1);
    vector <vector <pair <int, int>>> adj(N);
    vector <int> res(N, 1);
    REPD(u, N) {
        if (res[u]) {
            sort(ALL(adj[u]));
            REP(i, (int) adj[u].size() - 1) if (adj[u][i].fi == adj[u][i + 1].fi) {
                res[u] = 0;
                break;
            }
            if (res[u]) {
                order[u].emplace(sz[u], u);
                --C[u];
                if (u) {
                    sz[P[u]] += sz[u];
                    adj[P[u]].emplace_back(C[u], u);
                }
                continue;
            }
        }
        if (u) res[P[u]] = 0;
    }
    auto is_subtree = [&] (int u, int v) {
        for (auto [w, x]: adj[v]) {
            auto p = lower_bound(ALL(adj[u]), pair{w, -1});
            if (p == adj[u].end() || p->fi != w || sz[p->se] < sz[x]) return false;
        }
        return true;
    };
    FORD(u, N, 1) {
        if (!res[u]) {
            res[P[u]] = 0;
            continue;
        }
        if (order[u].size() > order[P[u]].size()) order[u].swap(order[P[u]]);
        for (auto &v: order[u]) {
            auto it = order[P[u]].insert(v).fi;
            if (it != order[P[u]].begin() && !is_subtree(v.se, it->se)) {
                res[P[u]] = 0;
                break;
            }
            if (next(it) != order[P[u]].end() && !is_subtree(next(it)->se, v.se)) {
                res[P[u]] = 0;
                break;
            }
        }
    }
    return res;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct

Subtask #1
0.0 / 9.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
3	Halted	0 KB	-

Subtask #2
0.0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
3	Halted	0 KB	-

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	76 ms	26812 KB	Output is correct
16	Correct	72 ms	25172 KB	Output is correct
17	Correct	80 ms	25532 KB	Output is correct
18	Correct	77 ms	26452 KB	Output is correct

Subtask #4
0.0 / 8.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
3	Halted	0 KB	-

Subtask #5
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	0 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
6	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 14.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
3	Halted	0 KB	-

Subtask #7
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	0 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
6	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 17.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
3	Halted	0 KB	-

Subtask #9
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	0 ms	348 KB	2nd lines differ - on the 1st token, expected: '0', found: '1'
6	Halted	0 ms	0 KB	-

답안 #914304

Compilation message