oj.uz

Submission #871460

# Submission time Handle Problem Language Result Execution time Memory
871460 2023-11-10T21:57:46 Z AdamGS Beech Tree (IOI23_beechtree) C++17
0 / 100
 43 ms 9840 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];
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;
  }
  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;
      |     ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 9.0

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

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 43 ms 9484 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 1 ms 860 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 752 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 12 ms 9840 KB Output is correct
12 Correct 7 ms 8028 KB Output is correct
13 Correct 8 ms 8796 KB Output is correct
14 Correct 8 ms 8944 KB Output is correct
15 Runtime error 27 ms 7252 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 43 ms 9484 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 0 ms 492 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

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

Subtask #7
0.0 / 12.0

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

Subtask #8
0.0 / 17.0

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

Subtask #9
0.0 / 12.0

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