oj.uz

Submission #1069147

# Submission time Handle Problem Language Result Execution time Memory
1069147 2024-08-21T16:25:50 Z bleahbleah Beech Tree (IOI23_beechtree) C++17
9 / 100
 2000 ms 72276 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e5 + 5;

vector<pii> g[nmax];
vector<int> P, C;

unordered_set<int> colors[nmax], play[nmax];
bool isanc(unordered_set<int>& A, unordered_set<int>& B) {
   if(sz(A) < sz(B)) return 0;
   for(auto &x : B)
      if(!A.count(x)) return 0;
   return 1;
}

vector<int> sol;
int h[nmax];

vector<int> dfs(int node) {
   //cerr << node << '\n';
   vector<int> here;
   sol[node] = 1;
   h[node] = 0;
   for(auto [x, e] : g[node]) {
      auto T = dfs(x);
      
      //cerr << x << ": " << sol[x] << '\n';
      
      sol[node] &= sol[x];
      copy(all(T), back_inserter(here));
      h[node] = max(h[node], h[x] + 1);
   }
   here.emplace_back(node);
   
   
   if(sol[node] == 0 || sz(g[node]) != sz(colors[node])) { sol[node] = 0; return here; }
   
   sort(all(here), [&](int a, int b) { return sz(colors[a]) > sz(colors[b]); });
   for(int i = 1; i < sz(here); i++) {
      if(!isanc(colors[here[i - 1]], colors[here[i]])) { sol[node] = 0; return here; }
   }
   
   vector<vector<int>> ts(h[node] + 1);
   for(auto x : here) ts[h[x]].emplace_back(x);
   
   for(auto x : here) play[x] = colors[x];
   
   for(int i = 0; i < h[node]; i++) {
         //if(node == 0) {
            //cerr << "niveaux " << i << '\n';
         //}
      for(auto x : here) {
         if(x == node) continue;
         if(h[x] < i) continue;
         
         //if(node == 0) {
            //cerr << x << '\n';
            //for(auto x : play)
         //}
         
         if(!isanc(play[P[x]], play[x])) { sol[node] = 0; return here; }
      }
      for(auto a : ts[i]) {
         if(a == node) continue;
         play[P[a]].erase(C[a]);
      }
   }
   
   for(auto x : here) {
      for(auto y : here) {
         if(sz(colors[x]) > sz(colors[y])) {
            if(h[x] < h[y]) { sol[node] = 0; return here; }
         }
      }
   }
   
   return here;
}

std::vector<int> beechtree(int N, int M, std::vector<int> P_, std::vector<int> C_) {
   P = P_;
   C = C_;
   for(int i = 1; i < N; i++) {
      g[P[i]].emplace_back(i, C[i]);
      colors[P[i]].emplace(C[i]);
   }
   sol.assign(N, 0);
   dfs(0);
   
   
   return sol;
}

/**
      Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/

Subtask #0
0.0 / 0.0

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

Subtask #1
9.0 / 9.0

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

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Runtime error 74 ms 72276 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 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13912 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 3 ms 13916 KB Output is correct
14 Correct 4 ms 13916 KB Output is correct
15 Runtime error 88 ms 49604 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Runtime error 74 ms 72276 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 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13944 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 3 ms 13916 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 3 ms 13916 KB Output is correct
16 Correct 3 ms 13916 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 4 ms 13912 KB Output is correct
20 Correct 3 ms 13916 KB Output is correct
21 Correct 3 ms 13916 KB Output is correct
22 Correct 3 ms 13916 KB Output is correct
23 Correct 3 ms 13912 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 3 ms 13912 KB Output is correct
27 Correct 3 ms 13912 KB Output is correct
28 Correct 3 ms 13916 KB Output is correct
29 Correct 4 ms 13916 KB Output is correct
30 Correct 3 ms 13916 KB Output is correct
31 Correct 3 ms 13916 KB Output is correct
32 Correct 3 ms 13912 KB Output is correct
33 Correct 3 ms 13916 KB Output is correct
34 Correct 3 ms 13916 KB Output is correct
35 Correct 3 ms 13916 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 3 ms 13916 KB Output is correct
38 Correct 3 ms 13916 KB Output is correct
39 Correct 3 ms 13916 KB Output is correct
40 Correct 3 ms 13916 KB Output is correct
41 Correct 3 ms 13916 KB Output is correct
42 Correct 3 ms 13916 KB Output is correct
43 Correct 3 ms 13916 KB Output is correct
44 Correct 3 ms 13912 KB Output is correct
45 Correct 3 ms 13916 KB Output is correct
46 Correct 3 ms 13916 KB Output is correct
47 Correct 3 ms 13916 KB Output is correct
48 Correct 16 ms 14168 KB Output is correct
49 Correct 4 ms 13912 KB Output is correct
50 Correct 3 ms 13916 KB Output is correct
51 Correct 4 ms 13972 KB Output is correct
52 Correct 3 ms 13916 KB Output is correct
53 Correct 3 ms 13912 KB Output is correct
54 Correct 4 ms 14168 KB Output is correct
55 Incorrect 3 ms 13916 KB 2nd lines differ - on the 82nd token, expected: '0', found: '1'
56 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 4 ms 13916 KB Output is correct
12 Correct 4 ms 13912 KB Output is correct
13 Correct 3 ms 13916 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 3 ms 13916 KB Output is correct
16 Correct 3 ms 13912 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 3 ms 13916 KB Output is correct
19 Correct 3 ms 13912 KB Output is correct
20 Correct 3 ms 13912 KB Output is correct
21 Correct 3 ms 13916 KB Output is correct
22 Correct 4 ms 13916 KB Output is correct
23 Correct 3 ms 13916 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Execution timed out 2085 ms 14832 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13944 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 3 ms 13916 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 3 ms 13916 KB Output is correct
16 Correct 3 ms 13916 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 4 ms 13912 KB Output is correct
20 Correct 3 ms 13916 KB Output is correct
21 Correct 3 ms 13916 KB Output is correct
22 Correct 3 ms 13916 KB Output is correct
23 Correct 3 ms 13912 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 3 ms 13912 KB Output is correct
27 Correct 3 ms 13912 KB Output is correct
28 Correct 3 ms 13916 KB Output is correct
29 Correct 4 ms 13916 KB Output is correct
30 Correct 3 ms 13916 KB Output is correct
31 Correct 3 ms 13916 KB Output is correct
32 Correct 3 ms 13912 KB Output is correct
33 Correct 3 ms 13916 KB Output is correct
34 Correct 3 ms 13916 KB Output is correct
35 Correct 3 ms 13916 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 3 ms 13916 KB Output is correct
38 Correct 16 ms 14168 KB Output is correct
39 Correct 4 ms 13912 KB Output is correct
40 Correct 3 ms 13916 KB Output is correct
41 Correct 4 ms 13972 KB Output is correct
42 Correct 3 ms 13916 KB Output is correct
43 Correct 3 ms 13916 KB Output is correct
44 Correct 3 ms 13916 KB Output is correct
45 Correct 3 ms 13916 KB Output is correct
46 Correct 3 ms 13916 KB Output is correct
47 Correct 3 ms 13916 KB Output is correct
48 Correct 3 ms 13912 KB Output is correct
49 Correct 3 ms 13916 KB Output is correct
50 Correct 3 ms 13916 KB Output is correct
51 Correct 3 ms 13916 KB Output is correct
52 Correct 3 ms 13916 KB Output is correct
53 Correct 3 ms 13916 KB Output is correct
54 Correct 3 ms 13916 KB Output is correct
55 Correct 4 ms 13916 KB Output is correct
56 Correct 3 ms 13916 KB Output is correct
57 Correct 3 ms 13912 KB Output is correct
58 Correct 4 ms 14168 KB Output is correct
59 Incorrect 3 ms 13916 KB 2nd lines differ - on the 82nd token, expected: '0', found: '1'
60 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 4 ms 13916 KB Output is correct
12 Correct 4 ms 13912 KB Output is correct
13 Correct 3 ms 13916 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 3 ms 13916 KB Output is correct
16 Correct 3 ms 13912 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 3 ms 13916 KB Output is correct
19 Correct 3 ms 13912 KB Output is correct
20 Correct 3 ms 13912 KB Output is correct
21 Correct 3 ms 13916 KB Output is correct
22 Correct 4 ms 13916 KB Output is correct
23 Correct 3 ms 13916 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Execution timed out 2085 ms 14832 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13944 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 3 ms 13916 KB Output is correct
8 Correct 3 ms 13916 KB Output is correct
9 Correct 3 ms 13916 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 3 ms 13916 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 3 ms 13916 KB Output is correct
16 Correct 3 ms 13916 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 4 ms 13916 KB Output is correct
19 Correct 4 ms 13912 KB Output is correct
20 Correct 3 ms 13916 KB Output is correct
21 Correct 3 ms 13916 KB Output is correct
22 Correct 3 ms 13916 KB Output is correct
23 Correct 3 ms 13912 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 3 ms 13912 KB Output is correct
27 Correct 3 ms 13912 KB Output is correct
28 Correct 3 ms 13916 KB Output is correct
29 Correct 4 ms 13916 KB Output is correct
30 Correct 3 ms 13916 KB Output is correct
31 Correct 3 ms 13916 KB Output is correct
32 Correct 3 ms 13912 KB Output is correct
33 Correct 3 ms 13916 KB Output is correct
34 Correct 3 ms 13916 KB Output is correct
35 Correct 3 ms 13916 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 3 ms 13916 KB Output is correct
38 Runtime error 74 ms 72276 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -