oj.uz

Submission #1069564

# Submission time Handle Problem Language Result Execution time Memory
1069564 2024-08-22T06:00:14 Z bleahbleah Beech Tree (IOI23_beechtree) C++17
0 / 100
 1 ms 604 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 = 2e3 + 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];

bool SI[nmax][nmax];
bool calc[nmax][nmax];

bool superimposable(int x, int y) { // x peste y 
   if(sz(g[x]) == 0 || x == y) return 1;
   if(calc[x][y]) return SI[x][y];
   map<int, int> gy;
   for(auto [a, c] : g[y]) gy[c] = a;
   calc[x][y] = 1;
   SI[x][y] = 1; 
   for(auto [a, c] : g[x]) {
      if(gy.count(c) == 0) { return SI[x][y] = 0; }
      if(!superimposable(a, gy[c])) { return SI[x][y] = 0; }
   }
   return 1;
}

int area[nmax];

vector<int> dfs(int node) {
   vector<int> here;
   sol[node] = 1;
   area[node] = 1;
   here.emplace_back(node);
   
   for(auto [x, c] : g[node]) {
      auto T = dfs(x);
      for(auto x : T) 
         for(auto y : T)
            sol[node] &= superimposable(x, y) || superimposable(y, x);
      area[node] += area[x];
      sol[node] &= sol[x];
      copy(all(T), back_inserter(here));
   }
   
   if(sz(g[node]) != sz(colors[node])) sol[node] = 0;
   if(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; }
   //}
   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 1 ms 604 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Incorrect 1 ms 604 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 0 ms 604 KB 2nd lines differ - on the 4th token, expected: '0', found: '1'
3 Halted 0 ms 0 KB -