oj.uz

Submission #841674

# Submission time Handle Problem Language Result Execution time Memory
841674 2023-09-01T20:24:42 Z Batrr Beech Tree (IOI23_beechtree) C++17
18 / 100
 2000 ms 123572 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

vector<pii> g[N];
int n, m;
int ans[N];
int P[N], C[N];
int tin[N], timer;

vector<int> t[N];

int sz[N];

map<int, int> was[N], dp[N];

bool f(int v, int u) {
    if (was[v][u])
        return dp[v][u];
    was[v][u] = 1;
    for (int i = 0, j = 0; i < g[u].size(); i++) {
        while (j < g[v].size() && g[v][j].f != g[u][i].f)
            j++;
        if (j == g[v].size())
            return dp[v][u] = false;
        if (!f(g[v][j].s, g[u][i].s))
            return dp[v][u] = false;
    }
    return dp[v][u] = true;
}

void dfs(int v) {
    tin[v] = timer++;
    sz[v] = 1;
    ans[v] = 1;
    t[v].pb(v);
    vector<int> a;
    for (int i = 0; i + 1 < g[v].size(); i++)
        ans[v] &= (g[v][i].f != g[v][i + 1].f);
    for (auto it: g[v]) {
        int to = it.s;
        a.pb(to);
        dfs(to);
        sz[v] += sz[to];
        ans[v] &= ans[to];
        ans[v] &= f(v, to);
        for(auto x : t[to])
            t[v].pb(x);
    }
    sort(a.begin(), a.end(), [](int i, int j) {
        return sz[i] > sz[j];
    });
    for (int i = 0; i + 1 < a.size(); i++)
        ans[v] &= f(a[i], a[i + 1]);

    sort(t[v].begin(), t[v].end(), [](int i, int j) {
        return g[i].size() < g[j].size();
    });
    set<int> st;
    for (int i = 0; i < t[v].size(); i++) {
        int u = t[v][i];
        vector<int> c;
        for (auto x: g[u]) {
            c.pb(x.f);
            st.insert(x.f);
        }
        vector<int> cc(st.begin(), st.end());
        ans[v] &= (c == cc);
    }
}

vector<int> beechtree(int N, int M, vector<int> PP, vector<int> CC) {

    n = N;
    for (int i = 0; i < n; i++) {
        g[i].clear();
        P[i] = PP[i];
        C[i] = CC[i];
        ans[i] = 0;
        was[i].clear();
        dp[i].clear();
        t[i].clear();
    }
    for (int i = 1; i < n; i++)
        g[P[i]].pb({C[i], i});
    for (int i = 0; i < n; i++)
        sort(g[i].begin(), g[i].end());

    dfs(0);


    return vector<int>(ans, ans + n);
}

Compilation message

beechtree.cpp: In function 'bool first(int, int)':
beechtree.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0, j = 0; i < g[u].size(); i++) {
      |                            ~~^~~~~~~~~~~~~
beechtree.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while (j < g[v].size() && g[v][j].f != g[u][i].f)
      |                ~~^~~~~~~~~~~~~
beechtree.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         if (j == g[v].size())
      |             ~~^~~~~~~~~~~~~~
beechtree.cpp:37:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |             return dp[v][u] = false;
beechtree.cpp:39:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   39 |             return dp[v][u] = false;
beechtree.cpp:41:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   41 |     return dp[v][u] = true;
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i + 1 < g[v].size(); i++)
      |                     ~~~~~~^~~~~~~~~~~~~
beechtree.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i + 1 < a.size(); i++)
      |                     ~~~~~~^~~~~~~~~~
beechtree.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < t[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 10 ms 48476 KB Output is correct
3 Correct 9 ms 48476 KB Output is correct

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 9 ms 48628 KB Output is correct
3 Correct 10 ms 48472 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48476 KB Output is correct
6 Correct 9 ms 48572 KB Output is correct
7 Correct 10 ms 48472 KB Output is correct
8 Correct 9 ms 48476 KB Output is correct
9 Correct 9 ms 48648 KB Output is correct
10 Correct 9 ms 48576 KB Output is correct
11 Correct 10 ms 48476 KB Output is correct
12 Correct 9 ms 48452 KB Output is correct
13 Correct 9 ms 48720 KB Output is correct
14 Correct 10 ms 48484 KB Output is correct
15 Correct 9 ms 48476 KB Output is correct
16 Correct 10 ms 48644 KB Output is correct
17 Correct 9 ms 48476 KB Output is correct
18 Correct 9 ms 48472 KB Output is correct
19 Correct 9 ms 48476 KB Output is correct
20 Correct 9 ms 48476 KB Output is correct
21 Correct 9 ms 48624 KB Output is correct
22 Correct 10 ms 48476 KB Output is correct
23 Correct 9 ms 48476 KB Output is correct
24 Correct 9 ms 48476 KB Output is correct
25 Correct 10 ms 48472 KB Output is correct
26 Correct 10 ms 48472 KB Output is correct
27 Correct 9 ms 48476 KB Output is correct
28 Correct 11 ms 48476 KB Output is correct
29 Correct 11 ms 48628 KB Output is correct
30 Correct 10 ms 48476 KB Output is correct
31 Correct 9 ms 48476 KB Output is correct
32 Correct 9 ms 48476 KB Output is correct
33 Correct 9 ms 48476 KB Output is correct
34 Correct 9 ms 48476 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 9 ms 48628 KB Output is correct
3 Correct 10 ms 48472 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48476 KB Output is correct
6 Correct 9 ms 48572 KB Output is correct
7 Execution timed out 2043 ms 123572 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 10 ms 48476 KB Output is correct
3 Correct 9 ms 48664 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48476 KB Output is correct
6 Correct 9 ms 48476 KB Output is correct
7 Correct 10 ms 48476 KB Output is correct
8 Correct 9 ms 48476 KB Output is correct
9 Correct 9 ms 48568 KB Output is correct
10 Correct 9 ms 48476 KB Output is correct
11 Correct 10 ms 48988 KB Output is correct
12 Correct 10 ms 48988 KB Output is correct
13 Correct 11 ms 48988 KB Output is correct
14 Correct 10 ms 48932 KB Output is correct
15 Correct 273 ms 94920 KB Output is correct
16 Correct 250 ms 89996 KB Output is correct
17 Correct 245 ms 92616 KB Output is correct
18 Correct 256 ms 94156 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 9 ms 48628 KB Output is correct
3 Correct 10 ms 48472 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Execution timed out 2043 ms 123572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 10 ms 48476 KB Output is correct
3 Correct 9 ms 48476 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48628 KB Output is correct
6 Correct 10 ms 48472 KB Output is correct
7 Correct 9 ms 48476 KB Output is correct
8 Correct 9 ms 48476 KB Output is correct
9 Correct 9 ms 48572 KB Output is correct
10 Correct 10 ms 48472 KB Output is correct
11 Correct 9 ms 48476 KB Output is correct
12 Correct 9 ms 48648 KB Output is correct
13 Correct 9 ms 48576 KB Output is correct
14 Correct 10 ms 48476 KB Output is correct
15 Correct 9 ms 48452 KB Output is correct
16 Correct 9 ms 48720 KB Output is correct
17 Correct 10 ms 48484 KB Output is correct
18 Correct 9 ms 48476 KB Output is correct
19 Correct 10 ms 48644 KB Output is correct
20 Correct 9 ms 48476 KB Output is correct
21 Correct 9 ms 48472 KB Output is correct
22 Correct 9 ms 48476 KB Output is correct
23 Correct 9 ms 48476 KB Output is correct
24 Correct 9 ms 48624 KB Output is correct
25 Correct 10 ms 48476 KB Output is correct
26 Correct 9 ms 48476 KB Output is correct
27 Correct 9 ms 48476 KB Output is correct
28 Correct 10 ms 48472 KB Output is correct
29 Correct 10 ms 48472 KB Output is correct
30 Correct 9 ms 48476 KB Output is correct
31 Correct 11 ms 48476 KB Output is correct
32 Correct 11 ms 48628 KB Output is correct
33 Correct 10 ms 48476 KB Output is correct
34 Correct 9 ms 48476 KB Output is correct
35 Correct 9 ms 48476 KB Output is correct
36 Correct 9 ms 48476 KB Output is correct
37 Correct 9 ms 48476 KB Output is correct
38 Correct 9 ms 48476 KB Output is correct
39 Correct 10 ms 48476 KB Output is correct
40 Correct 9 ms 48664 KB Output is correct
41 Correct 9 ms 48476 KB Output is correct
42 Correct 9 ms 48476 KB Output is correct
43 Correct 9 ms 48476 KB Output is correct
44 Correct 10 ms 48476 KB Output is correct
45 Correct 9 ms 48476 KB Output is correct
46 Correct 9 ms 48568 KB Output is correct
47 Correct 9 ms 48476 KB Output is correct
48 Correct 11 ms 48728 KB Output is correct
49 Correct 10 ms 48732 KB Output is correct
50 Correct 11 ms 48732 KB Output is correct
51 Correct 23 ms 48800 KB Output is correct
52 Correct 10 ms 48732 KB Output is correct
53 Correct 10 ms 48476 KB Output is correct
54 Correct 11 ms 48732 KB Output is correct
55 Incorrect 10 ms 48728 KB 2nd lines differ - on the 82nd token, expected: '0', found: '1'
56 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 9 ms 48628 KB Output is correct
3 Correct 10 ms 48472 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48648 KB Output is correct
6 Correct 9 ms 48576 KB Output is correct
7 Correct 10 ms 48476 KB Output is correct
8 Correct 9 ms 48452 KB Output is correct
9 Correct 9 ms 48720 KB Output is correct
10 Correct 10 ms 48484 KB Output is correct
11 Correct 9 ms 48476 KB Output is correct
12 Correct 10 ms 48644 KB Output is correct
13 Correct 9 ms 48476 KB Output is correct
14 Correct 9 ms 48472 KB Output is correct
15 Correct 9 ms 48476 KB Output is correct
16 Correct 9 ms 48476 KB Output is correct
17 Correct 9 ms 48624 KB Output is correct
18 Correct 10 ms 48476 KB Output is correct
19 Correct 9 ms 48476 KB Output is correct
20 Correct 9 ms 48476 KB Output is correct
21 Correct 10 ms 48472 KB Output is correct
22 Correct 10 ms 48472 KB Output is correct
23 Correct 9 ms 48476 KB Output is correct
24 Correct 11 ms 48476 KB Output is correct
25 Correct 140 ms 59896 KB Output is correct
26 Correct 141 ms 59952 KB Output is correct
27 Correct 136 ms 59876 KB Output is correct
28 Correct 148 ms 59888 KB Output is correct
29 Correct 141 ms 59988 KB Output is correct
30 Correct 22 ms 50264 KB Output is correct
31 Correct 17 ms 50268 KB Output is correct
32 Correct 15 ms 49756 KB Output is correct
33 Incorrect 16 ms 49500 KB 2nd lines differ - on the 1481st token, expected: '0', found: '1'
34 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 10 ms 48476 KB Output is correct
3 Correct 9 ms 48476 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48628 KB Output is correct
6 Correct 10 ms 48472 KB Output is correct
7 Correct 9 ms 48476 KB Output is correct
8 Correct 9 ms 48476 KB Output is correct
9 Correct 9 ms 48572 KB Output is correct
10 Correct 10 ms 48472 KB Output is correct
11 Correct 9 ms 48476 KB Output is correct
12 Correct 9 ms 48648 KB Output is correct
13 Correct 9 ms 48576 KB Output is correct
14 Correct 10 ms 48476 KB Output is correct
15 Correct 9 ms 48452 KB Output is correct
16 Correct 9 ms 48720 KB Output is correct
17 Correct 10 ms 48484 KB Output is correct
18 Correct 9 ms 48476 KB Output is correct
19 Correct 10 ms 48644 KB Output is correct
20 Correct 9 ms 48476 KB Output is correct
21 Correct 9 ms 48472 KB Output is correct
22 Correct 9 ms 48476 KB Output is correct
23 Correct 9 ms 48476 KB Output is correct
24 Correct 9 ms 48624 KB Output is correct
25 Correct 10 ms 48476 KB Output is correct
26 Correct 9 ms 48476 KB Output is correct
27 Correct 9 ms 48476 KB Output is correct
28 Correct 10 ms 48472 KB Output is correct
29 Correct 10 ms 48472 KB Output is correct
30 Correct 9 ms 48476 KB Output is correct
31 Correct 11 ms 48476 KB Output is correct
32 Correct 11 ms 48628 KB Output is correct
33 Correct 10 ms 48476 KB Output is correct
34 Correct 9 ms 48476 KB Output is correct
35 Correct 9 ms 48476 KB Output is correct
36 Correct 9 ms 48476 KB Output is correct
37 Correct 9 ms 48476 KB Output is correct
38 Correct 11 ms 48728 KB Output is correct
39 Correct 10 ms 48732 KB Output is correct
40 Correct 11 ms 48732 KB Output is correct
41 Correct 23 ms 48800 KB Output is correct
42 Correct 9 ms 48476 KB Output is correct
43 Correct 10 ms 48476 KB Output is correct
44 Correct 9 ms 48664 KB Output is correct
45 Correct 9 ms 48476 KB Output is correct
46 Correct 9 ms 48476 KB Output is correct
47 Correct 9 ms 48476 KB Output is correct
48 Correct 10 ms 48476 KB Output is correct
49 Correct 9 ms 48476 KB Output is correct
50 Correct 9 ms 48568 KB Output is correct
51 Correct 9 ms 48476 KB Output is correct
52 Correct 10 ms 48988 KB Output is correct
53 Correct 10 ms 48988 KB Output is correct
54 Correct 11 ms 48988 KB Output is correct
55 Correct 10 ms 48932 KB Output is correct
56 Correct 10 ms 48732 KB Output is correct
57 Correct 10 ms 48476 KB Output is correct
58 Correct 11 ms 48732 KB Output is correct
59 Incorrect 10 ms 48728 KB 2nd lines differ - on the 82nd token, expected: '0', found: '1'
60 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 9 ms 48628 KB Output is correct
3 Correct 10 ms 48472 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48648 KB Output is correct
6 Correct 9 ms 48576 KB Output is correct
7 Correct 10 ms 48476 KB Output is correct
8 Correct 9 ms 48452 KB Output is correct
9 Correct 9 ms 48720 KB Output is correct
10 Correct 10 ms 48484 KB Output is correct
11 Correct 9 ms 48476 KB Output is correct
12 Correct 10 ms 48644 KB Output is correct
13 Correct 9 ms 48476 KB Output is correct
14 Correct 9 ms 48472 KB Output is correct
15 Correct 9 ms 48476 KB Output is correct
16 Correct 9 ms 48476 KB Output is correct
17 Correct 9 ms 48624 KB Output is correct
18 Correct 10 ms 48476 KB Output is correct
19 Correct 9 ms 48476 KB Output is correct
20 Correct 9 ms 48476 KB Output is correct
21 Correct 10 ms 48472 KB Output is correct
22 Correct 10 ms 48472 KB Output is correct
23 Correct 9 ms 48476 KB Output is correct
24 Correct 11 ms 48476 KB Output is correct
25 Correct 140 ms 59896 KB Output is correct
26 Correct 141 ms 59952 KB Output is correct
27 Correct 136 ms 59876 KB Output is correct
28 Correct 148 ms 59888 KB Output is correct
29 Correct 141 ms 59988 KB Output is correct
30 Correct 22 ms 50264 KB Output is correct
31 Correct 17 ms 50268 KB Output is correct
32 Correct 15 ms 49756 KB Output is correct
33 Incorrect 16 ms 49500 KB 2nd lines differ - on the 1481st token, expected: '0', found: '1'
34 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 48476 KB Output is correct
2 Correct 10 ms 48476 KB Output is correct
3 Correct 9 ms 48476 KB Output is correct
4 Correct 9 ms 48476 KB Output is correct
5 Correct 9 ms 48628 KB Output is correct
6 Correct 10 ms 48472 KB Output is correct
7 Correct 9 ms 48476 KB Output is correct
8 Correct 9 ms 48476 KB Output is correct
9 Correct 9 ms 48572 KB Output is correct
10 Correct 10 ms 48472 KB Output is correct
11 Correct 9 ms 48476 KB Output is correct
12 Correct 9 ms 48648 KB Output is correct
13 Correct 9 ms 48576 KB Output is correct
14 Correct 10 ms 48476 KB Output is correct
15 Correct 9 ms 48452 KB Output is correct
16 Correct 9 ms 48720 KB Output is correct
17 Correct 10 ms 48484 KB Output is correct
18 Correct 9 ms 48476 KB Output is correct
19 Correct 10 ms 48644 KB Output is correct
20 Correct 9 ms 48476 KB Output is correct
21 Correct 9 ms 48472 KB Output is correct
22 Correct 9 ms 48476 KB Output is correct
23 Correct 9 ms 48476 KB Output is correct
24 Correct 9 ms 48624 KB Output is correct
25 Correct 10 ms 48476 KB Output is correct
26 Correct 9 ms 48476 KB Output is correct
27 Correct 9 ms 48476 KB Output is correct
28 Correct 10 ms 48472 KB Output is correct
29 Correct 10 ms 48472 KB Output is correct
30 Correct 9 ms 48476 KB Output is correct
31 Correct 11 ms 48476 KB Output is correct
32 Correct 11 ms 48628 KB Output is correct
33 Correct 10 ms 48476 KB Output is correct
34 Correct 9 ms 48476 KB Output is correct
35 Correct 9 ms 48476 KB Output is correct
36 Correct 9 ms 48476 KB Output is correct
37 Correct 9 ms 48476 KB Output is correct
38 Execution timed out 2043 ms 123572 KB Time limit exceeded
39 Halted 0 ms 0 KB -