oj.uz

Submission #842330

# Submission time Handle Problem Language Result Execution time Memory
842330 2023-09-02T18:38:30 Z Itamar Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 27096 KB 
//#include "beechtree.h"
#include <cassert>
#include <cstdio>
#include <cassert>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
using namespace std;
#pragma warning(disable : 4996)
#define vi vector<int>
const int siz = 2001;
const int siz2 = 2001;
vi son[siz];
int pad[siz];
int sub[siz];
int subc[siz][siz2];
bool g[siz][siz2];
int nonsubc[siz][siz2];
int h[siz];
int num[siz];
#include <algorithm>
void dfs1(int i) {
    sub[i] = 1;
    for (int f : son[i]) {
        dfs1(f);
        sub[i] += sub[f];
        
    }
}
bool fun(int i, int j) {
    return sub[j] < sub[i];
}
#include <queue>
int col[siz];
int n;
void dfs2(int i, int c) {
    int f = 0;
    for (int s : son[i]) {
        dfs2(s, c);
        if (col[s] == c)f++;
        subc[i][c] = max(subc[i][c], subc[s][c]);
        nonsubc[i][c] = min(nonsubc[i][c], nonsubc[s][c]);
        g[i][c] &= g[s][c];
    }
    if (f > 1)g[i][c] = 0;
    if (f == 1)subc[i][c] = max(subc[i][c], num[i]);
    else nonsubc[i][c] = min(nonsubc[i][c], num[i]);
    if ((subc[i][c] >= 0) && (nonsubc[i][c] <= n) && (subc[i][c] >= nonsubc[i][c]))g[i][c] = 0;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    n = N;
    pad[0] = 0;
    for (int i = 1; i < N; i++) {
        pad[i] = P[i];
        son[P[i]].push_back(i);
    }
    for (int i = 0; i < N; i++)col[i] = C[i];
    dfs1(0);
    for (int i = 0; i < N; i++) {
        sort(son[i].begin(), son[i].end(), fun);
    }
    queue<int> q;
    q.push(0);
    int t = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        num[v] = t;
        t++;
        for (int f : son[v]) {
            q.push(f);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= M; j++) {
            subc[i][j] = -1;
            nonsubc[i][j] = N + 1;
            g[i][j] = 1;
        }
    }
    for (int i = 1; i <= M; i++) {
        dfs2(0, i);
    }
    vector<int> ans(N,1);
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= M; j++) {
            ans[i] = ((ans[i])&(g[i][j]));
        }
    }
    return ans;
}

Compilation message

beechtree.cpp:12: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
   12 | #pragma warning(disable : 4996)
      |

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Runtime error 33 ms 7020 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6776 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Execution timed out 2057 ms 27096 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Runtime error 33 ms 7020 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Incorrect 1 ms 4444 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Incorrect 1 ms 4444 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4440 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Incorrect 1 ms 4444 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -