oj.uz

Submission #1061872

# Submission time Handle Problem Language Result Execution time Memory
1061872 2024-08-16T14:36:27 Z dozer Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 28988 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 adj[a.st].size()> adj[b.st].size();
        });
    }
    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 3 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 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 2 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 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 2 ms 8280 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 8280 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 3 ms 8284 KB Output is correct
17 Correct 2 ms 8280 KB Output is correct
18 Correct 2 ms 8284 KB Output is correct
19 Correct 2 ms 8480 KB Output is correct
20 Incorrect 2 ms 8284 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 2 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 3 ms 8284 KB Output is correct
7 Execution timed out 2068 ms 28988 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 8280 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 3 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 9308 KB Output is correct
12 Correct 19 ms 9308 KB Output is correct
13 Correct 22 ms 9304 KB Output is correct
14 Correct 18 ms 9308 KB Output is correct
15 Correct 1635 ms 13384 KB Output is correct
16 Correct 1542 ms 13200 KB Output is correct
17 Correct 1459 ms 13276 KB Output is correct
18 Correct 1661 ms 13340 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 3 ms 8284 KB Output is correct
4 Correct 2 ms 8280 KB Output is correct
5 Execution timed out 2068 ms 28988 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

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