oj.uz

Submission #1061922

# Submission time Handle Problem Language Result Execution time Memory
1061922 2024-08-16T15:23:35 Z mychecksedad Beech Tree (IOI23_beechtree) C++17
17 / 100
 83 ms 67668 KB 
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
#define vi vector<int>
const int N = 200005;
const ll INF = 1e18;

vector<int> g[N], s[N];
vi res;
int antidep[N], sz[N], col[N], n, m, par[N];
bool ok = 1;
void dfs(int v){
  set<int> s;
  antidep[v] = 0;
  int co = 0, node;
  sz[v] = 1;
  for(int u: g[v]){
    dfs(u);
    sz[v] += sz[u];
    par[u] = v;
    s.insert(col[u]);
    antidep[v] = max(antidep[u] + 1, antidep[v]);
    if(g[u].size() > 0) co++, node = u;
  }
  sort(all(g[v]), [&](const int &x, const int &y){
    return sz[x] > sz[y];
  });

  // cout << v << ' ' << antidep[v] << '\n';
  if(g[v].size() == 0){
    res[v] = 1;
  }else if(s.size() == g[v].size() && antidep[v] == 1){
    res[v] = 1;
  }else{
    if(antidep[v] > 2){
      res[v] = 0;
    }else{  
      if(s.size() != g[v].size()){
        res[v] = 0;
        return;
      }
        g[v].insert(g[v].begin(), v);
        // for(int x: g[node]){
        //   s.insert(col[x]);
        // }
        // if(s.size() == g[v].size()){
        //   res[v] = 1;
        // }else{
        //   res[v] = 0;
        // }
        res[v] = 1;
        for(int i = 1; i < g[v].size(); ++i) if(res[g[v][i]] == 0) res[v] = 0;
        for(int i = 0; i + 1 < g[v].size(); ++i){
          set<int> s;
          int u = g[v][i];
          for(int j = 0; j < g[u].size(); ++j) s.insert(col[g[u][j]]); 
            int x = s.size();
          u = g[v][i + 1];
          for(int j = 0; j < g[u].size(); ++j) s.insert(col[g[u][j]]); 
            int y = s.size();
          if(x != y){
            res[v] = 0;
            break;
          }
        }
    }
  }
}
std::vector<int> beechtree(int nn, int mm, std::vector<int> P, std::vector<int> C)
{n=nn, m=mm;
  res.resize(n);
  for(int i = 1; i < n; ++i){
    g[P[i]].pb(i);
    col[i] = C[i];
  }
  // dfs(0);
  // bool ok = 1;
  // res[n - 1] = 1;
  // for(int i = n - 2; i >= 0; --i){
  //   if(ok == 0){
  //     res[i] = ok;
  //   }else if(C[i] != C[i + 1]){
  //     res[i] = 1;
  //     ok = 0;
  //   }else{
  //     res[i] = 1;
  //   }
  // }
  dfs(0);
  return res;
}

Compilation message

beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:57:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i = 1; i < g[v].size(); ++i) if(res[g[v][i]] == 0) res[v] = 0;
      |                        ~~^~~~~~~~~~~~~
beechtree.cpp:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int i = 0; i + 1 < g[v].size(); ++i){
      |                        ~~~~~~^~~~~~~~~~~~~
beechtree.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |           for(int j = 0; j < g[u].size(); ++j) s.insert(col[g[u][j]]);
      |                          ~~^~~~~~~~~~~~~
beechtree.cpp:64:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |           for(int j = 0; j < g[u].size(); ++j) s.insert(col[g[u][j]]);
      |                          ~~^~~~~~~~~~~~~
beechtree.cpp:20:15: warning: variable 'node' set but not used [-Wunused-but-set-variable]
   20 |   int co = 0, node;
      |               ^~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12724 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12720 KB Output is correct
6 Correct 2 ms 12632 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 3 ms 12636 KB Output is correct
15 Correct 34 ms 16616 KB Output is correct
16 Correct 31 ms 16476 KB Output is correct
17 Correct 30 ms 16476 KB Output is correct
18 Correct 45 ms 16724 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 80 ms 67668 KB Output is correct
6 Correct 79 ms 67640 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 ms 12888 KB Output is correct
10 Correct 3 ms 12636 KB Output is correct
11 Correct 65 ms 23456 KB Output is correct
12 Correct 83 ms 18772 KB Output is correct

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12648 KB Output is correct
15 Correct 2 ms 12632 KB Output is correct
16 Incorrect 2 ms 12632 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Correct 2 ms 12636 KB Output is correct
14 Correct 2 ms 12648 KB Output is correct
15 Correct 2 ms 12632 KB Output is correct
16 Incorrect 2 ms 12632 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

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