oj.uz

Submission #1061390

# Submission time Handle Problem Language Result Execution time Memory
1061390 2024-08-16T08:32:59 Z dozer Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 28992 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005

vector<pii> adj[MAXN];
int sz[MAXN];

void dfs(int node){
    sz[node] = 1;
    for (auto i :adj[node]){
        dfs(i.st);
        sz[node] += sz[i.st];
    }
}

vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    for (int i = 0; i < N; i++) adj[i].clear();   
    for (int i = 1; i < N; i++){
        adj[P[i]].pb({i, C[i]});
    }

    dfs(0);
    for (int i = 0; i < N; i++){
        sort(adj[i].begin(), adj[i].end(), [&](pii a, pii b){
            return sz[a.st] > sz[b.st];
        });
    }
    int n = N;
    vector<int> ans(N, 1);
    for (int i = n - 1; i >= 0; i--){
        vector<int> curr, cnt(M + 2, 0);
        queue<int> q;
        q.push(i);
        curr.pb(i);
        while(!q.empty()){
            int top = q.front();
            q.pop();
            for (auto j : adj[top]){
                if (curr[cnt[C[j.st]]] != P[j.st]) ans[i] = 0;
                curr.pb(j.st);
                cnt[C[j.st]]++;
                q.push(j.st);
            }
        }
    }

    return ans;
}
/*
int main()
{
    fileio();
    int N, M;
    assert(2 == scanf("%d %d", &N, &M));
    std::vector<int> P(N);
    for (int i = 0; i < N; ++i)
        assert(1 == scanf("%d", &P[i]));
    std::vector<int> C(N);
    for (int i = 0; i < N; ++i)
        assert(1 == scanf("%d", &C[i]));

    fclose(stdin);

    std::vector<int> res = beechtree(N, M, P, C);

    int n = res.size();
    for (int i = 0; i < n; ++i)
    {
        if (i > 0)
            printf(" ");
        printf("%d", res[i]);
    }
    printf("\n");
    fclose(stdout);

    return 0;
}*/

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Correct 2 ms 8284 KB Output is correct
8 Correct 2 ms 8296 KB Output is correct
9 Correct 2 ms 8360 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 2 ms 8284 KB Output is correct
14 Correct 2 ms 8284 KB Output is correct
15 Correct 2 ms 8284 KB Output is correct
16 Correct 2 ms 8284 KB Output is correct
17 Correct 2 ms 8284 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8284 KB Output is correct
20 Incorrect 2 ms 8256 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 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8284 KB Output is correct
7 Execution timed out 2013 ms 28992 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 3 ms 8288 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8368 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 20 ms 9312 KB Output is correct
12 Correct 17 ms 9320 KB Output is correct
13 Correct 18 ms 9308 KB Output is correct
14 Correct 18 ms 9320 KB Output is correct
15 Correct 1591 ms 14428 KB Output is correct
16 Correct 1440 ms 14144 KB Output is correct
17 Correct 1501 ms 14252 KB Output is correct
18 Correct 1489 ms 14400 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8296 KB Output is correct
5 Execution timed out 2013 ms 28992 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

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