oj.uz

Submission #872097

# Submission time Handle Problem Language Result Execution time Memory
872097 2023-11-12T10:03:28 Z AdamGS Beech Tree (IOI23_beechtree) C++17
0 / 100
 38 ms 13672 KB 
#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7;
vector<pair<int,int>>V[LIM];
int T[LIM][LIM], czy[LIM], ile[LIM], cnt[200007];
void DFS(int x) {
  czy[x]=ile[x]=1;
  for(int i=1; i<V[x].size(); ++i) if(V[x][i].st==V[x][i-1].st) czy[x]=0;
  for(auto i : V[x]) {
    DFS(i.nd);
    ile[x]+=ile[i.nd];
    if(!czy[i.nd]) czy[x]=0;
  }
}
int wiekszy(int x, int y) {
  if(T[x][y]!=0) return T[x][y];
  T[x][y]=1;
  int l=0;
  for(auto i : V[y]) {
    while(l<V[x].size() && V[x][l].st<i.st) ++l;
    if(l==V[x].size() || V[x][l].st>i.st) {
      T[x][y]=-1;
      break;
    }
    if(wiekszy(V[x][l].nd, i.nd)==-1) {
      T[x][y]=-1;
      break;
      }
    ++l;
  }
  return T[x][y];
}
vector<int>beechtree(int n, int m, vector<int>P, vector<int>C) {
  rep(i, n-1) V[P[i+1]].pb({C[i+1], i+1});
  rep(i, n) sort(all(V[i]));
  DFS(0);
  for(int i=n-1; i>=0; --i) for(int j=n-1; j>i; --j) {
    wiekszy(i, j);
    wiekszy(j, i);
  }
  vector<int>ans(n);
  rep(i, n) ans[i]=czy[i];
  for(int i=n-1; i>=0; --i) {
    vector<pair<int,int>>S;
    for(auto j : V[i]) {
      if(!ans[j.nd]) ans[i]=0;
      S.pb({ile[j.nd], j.nd});
    }
    sort(all(S));
    rep(a, S.size()) rep(b, a) if(T[S[a].nd][S[b].nd]==-1) ans[i]=0;
    rep(a, S.size()) if(T[i][S[a].nd]==-1) ans[i]=0;
    if(!ans[i]) continue;
    for(int j=1; j<S.size(); ++j) cnt[C[S[j].nd]]=0;
    for(int j=1; j<S.size(); ++j) {
      int x=S[j].nd;
      if(S[cnt[C[x]]].nd!=P[x]) ans[i]=0;
      ++cnt[C[x]];
    }
  }
  return ans;
}

Compilation message

beechtree.cpp: In function 'void DFS(int)':
beechtree.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i=1; i<V[x].size(); ++i) if(V[x][i].st==V[x][i-1].st) czy[x]=0;
      |                ~^~~~~~~~~~~~
beechtree.cpp: In function 'int wiekszy(int, int)':
beechtree.cpp:26:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(l<V[x].size() && V[x][l].st<i.st) ++l;
      |           ~^~~~~~~~~~~~
beechtree.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(l==V[x].size() || V[x][l].st>i.st) {
      |        ~^~~~~~~~~~~~~
beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
beechtree.cpp:56:5: note: in expansion of macro 'rep'
   56 |     rep(a, S.size()) rep(b, a) if(T[S[a].nd][S[b].nd]==-1) ans[i]=0;
      |     ^~~
beechtree.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
beechtree.cpp:57:5: note: in expansion of macro 'rep'
   57 |     rep(a, S.size()) if(T[i][S[a].nd]==-1) ans[i]=0;
      |     ^~~
beechtree.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int j=1; j<S.size(); ++j) cnt[C[S[j].nd]]=0;
      |                  ~^~~~~~~~~
beechtree.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int j=1; j<S.size(); ++j) {
      |                  ~^~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4564 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4564 KB Output is correct
7 Runtime error 38 ms 13672 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 Incorrect 1 ms 4560 KB 2nd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

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

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

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