Submission #871459

#	Time	Username	Problem	Language	Result	Execution time	Memory
871459		AdamGS	Beech Tree (IOI23_beechtree)	C++17	0 / 100	1 ms	1116 KiB

beechtree

#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];
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;
  }
  return ans;
}

Compilation message (stderr)

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;
      |     ^~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12