oj.uz

Submission #841670

# Submission time Handle Problem Language Result Execution time Memory
841670 2023-09-01T20:01:01 Z Batrr Beech Tree (IOI23_beechtree) C++17
17 / 100
 2000 ms 63404 KB 
#include "beechtree.h"
#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];

bool f(int v, int u) {
    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 false;
        if (!f(g[v][j].s, g[u][i].s))
            return false;
    }
    return true;
}

void dfs(int v) {
    tin[v] = timer++;
    sz[v] = 1;
    ans[v] = 1;
    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);
    }
    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]);

}

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;
    }
    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:29: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]
   29 |     for (int i = 0, j = 0; i < g[u].size(); i++) {
      |                            ~~^~~~~~~~~~~~~
beechtree.cpp:30: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]
   30 |         while (j < g[v].size() && g[v][j].f != g[u][i].f)
      |                ~~^~~~~~~~~~~~~
beechtree.cpp:32: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]
   32 |         if (j == g[v].size())
      |             ~~^~~~~~~~~~~~~~
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i + 1 < g[v].size(); i++)
      |                    ~~~~~~^~~~~~~~~~~~~
beechtree.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i + 1 < a.size(); i++)
      |                     ~~~~~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20060 KB Output is correct
3 Correct 4 ms 20252 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20152 KB Output is correct
3 Correct 4 ms 20060 KB Output is correct
4 Correct 4 ms 20060 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 4 ms 20060 KB Output is correct
11 Correct 4 ms 20060 KB Output is correct
12 Correct 4 ms 20056 KB Output is correct
13 Correct 4 ms 20060 KB Output is correct
14 Incorrect 4 ms 20060 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
15 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20152 KB Output is correct
3 Correct 4 ms 20060 KB Output is correct
4 Correct 4 ms 20060 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 84 ms 60992 KB Output is correct
8 Correct 87 ms 63404 KB Output is correct
9 Correct 5 ms 20060 KB Output is correct
10 Correct 4 ms 20060 KB Output is correct
11 Correct 4 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 17 ms 20660 KB Output is correct
14 Correct 14 ms 20568 KB Output is correct
15 Correct 5 ms 20572 KB Output is correct
16 Correct 5 ms 20600 KB Output is correct
17 Execution timed out 2054 ms 63316 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20060 KB Output is correct
3 Correct 4 ms 20060 KB Output is correct
4 Correct 4 ms 20060 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20108 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 4 ms 20060 KB Output is correct
11 Correct 4 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 4 ms 20060 KB Output is correct
14 Correct 5 ms 20060 KB Output is correct
15 Correct 36 ms 23484 KB Output is correct
16 Correct 39 ms 23388 KB Output is correct
17 Correct 34 ms 23460 KB Output is correct
18 Correct 36 ms 23544 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20152 KB Output is correct
3 Correct 4 ms 20060 KB Output is correct
4 Correct 4 ms 20060 KB Output is correct
5 Correct 84 ms 60992 KB Output is correct
6 Correct 87 ms 63404 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 5 ms 20312 KB Output is correct
10 Correct 4 ms 20316 KB Output is correct
11 Correct 69 ms 31916 KB Output is correct
12 Correct 65 ms 27996 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20060 KB Output is correct
3 Correct 4 ms 20252 KB Output is correct
4 Correct 4 ms 20056 KB Output is correct
5 Correct 4 ms 20152 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 4 ms 20060 KB Output is correct
11 Correct 4 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 4 ms 20060 KB Output is correct
14 Correct 4 ms 20060 KB Output is correct
15 Correct 4 ms 20056 KB Output is correct
16 Correct 4 ms 20060 KB Output is correct
17 Incorrect 4 ms 20060 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20152 KB Output is correct
3 Correct 4 ms 20060 KB Output is correct
4 Correct 4 ms 20060 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20056 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Incorrect 4 ms 20060 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20060 KB Output is correct
3 Correct 4 ms 20252 KB Output is correct
4 Correct 4 ms 20056 KB Output is correct
5 Correct 4 ms 20152 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 4 ms 20060 KB Output is correct
11 Correct 4 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 4 ms 20060 KB Output is correct
14 Correct 4 ms 20060 KB Output is correct
15 Correct 4 ms 20056 KB Output is correct
16 Correct 4 ms 20060 KB Output is correct
17 Incorrect 4 ms 20060 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20152 KB Output is correct
3 Correct 4 ms 20060 KB Output is correct
4 Correct 4 ms 20060 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20056 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Incorrect 4 ms 20060 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
11 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20056 KB Output is correct
2 Correct 4 ms 20060 KB Output is correct
3 Correct 4 ms 20252 KB Output is correct
4 Correct 4 ms 20056 KB Output is correct
5 Correct 4 ms 20152 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 4 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20060 KB Output is correct
10 Correct 4 ms 20060 KB Output is correct
11 Correct 4 ms 20060 KB Output is correct
12 Correct 4 ms 20060 KB Output is correct
13 Correct 4 ms 20060 KB Output is correct
14 Correct 4 ms 20060 KB Output is correct
15 Correct 4 ms 20056 KB Output is correct
16 Correct 4 ms 20060 KB Output is correct
17 Incorrect 4 ms 20060 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -