oj.uz

Submission #955867

# Submission time Handle Problem Language Result Execution time Memory
955867 2024-03-31T15:50:53 Z Dan4Life Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 548 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

const int mxN = (int)2000;
int n, m;
vector<int> ans, col, par, adj[mxN];
vector<int> sub[mxN];

void dfs(int s, int p){
    sub[s].pb(s);
    for(auto u : adj[s]){
        if(u==p) continue;
        dfs(u,s);
        for(auto child : sub[u]) 
            sub[s].pb(child);
    }
    if(sz(sub[s])==1) ans[s] = 1;
    sort(all(sub[s]));
    do{
        bool ok = 1; if(sub[s][0]!=s) continue;
        for(int i = 1; i < sz(sub[s]); i++){
            int f = 0, node = sub[s][i];
            int cur_col = col[node];
            for(int j = 0; j < i; j++){
                int nodej = sub[s][j];
                int chk_col = col[nodej];
                if(chk_col==cur_col) f++;
            }
            if(par[node]!=sub[s][f]) ok = 0;
        }
        if(ok) ans[s]=1;
    }while(next_permutation(all(sub[s])));
}

vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
    n = N, m = M;
    ans.clear(); col.clear(); par.clear();
    for(int i = 0; i < N; i++) 
        sub[i].clear(), adj[i].clear();

    for(int i = 0; i < N; i++) ans.pb(0);
    for(auto u : C) col.pb(u);
    for(auto u : P) par.pb(u);
    for(int i = 1; i < N; i++){
        adj[P[i]].pb(i);
        adj[i].pb(P[i]);
    }
    dfs(0,-1); return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2075 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2075 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2075 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2075 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -