Submission #955943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
955943	2024-03-31T17:50:31 Z	Dan4Life	Beech Tree (IOI23_beechtree)	C++17	9 / 100	2000 ms	9500 KB

beechtree

#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 = 1; 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	532 KB	Output is correct
2	Execution timed out	2062 ms	348 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	528 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	704 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	1 ms	600 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	1 ms	348 KB	Output is correct

Subtask #2
0.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Runtime error	37 ms	9500 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	Execution timed out	2061 ms	348 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	528 KB	Output is correct
4	Correct	0 ms	596 KB	Output is correct
5	Runtime error	37 ms	9500 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	532 KB	Output is correct
2	Execution timed out	2062 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	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	528 KB	Output is correct
4	Correct	0 ms	596 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	704 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Execution timed out	2005 ms	856 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	532 KB	Output is correct
2	Execution timed out	2062 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	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	528 KB	Output is correct
4	Correct	0 ms	596 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	704 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Execution timed out	2005 ms	856 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 12.0

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

Submission #955943

Compilation message