oj.uz

Submission #955856

# Submission time Handle Problem Language Result Execution time Memory
955856 2024-03-31T15:32:17 Z Dan4Life Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 600 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)20;
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);
    }
    vector<int> v(sz(sub[s]),0); iota(all(v),0);
    do{
        bool ok = 1; if(v[0]!=0) continue;
        for(int i = 0; i < sz(v); i++){
            int f = 0, node = sub[s][v[i]];
            int cur_col = col[node];
            for(int j = 0; j < i; j++){
                int nodej = sub[s][v[j]];
                int chk_col = col[nodej];
                if(chk_col==cur_col) f++;
            }
            if(i and par[node]!=sub[s][v[f]]) ok = 0;
        }
        if(ok) { ans[s] = 1; break; }
    }while(next_permutation(all(v)));
}

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

    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 0 ms 600 KB Output is correct
2 Execution timed out 2086 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 Runtime error 1 ms 344 KB Execution killed with signal 11
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 0 ms 600 KB Output is correct
2 Execution timed out 2086 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 0 ms 600 KB Output is correct
2 Execution timed out 2086 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 0 ms 600 KB Output is correct
2 Execution timed out 2086 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -