Submission #914304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914304	2024-01-21T15:03:53 Z	marvinthang	Beech Tree (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

#	Verdict	Execution time	Memory	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

#	Verdict	Memory	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

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #914304

Compilation message