Submission #135697

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
135697	2019-07-24 09:51:24	khsoo01	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	591 ms	173944 KiB

catinatree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N = 200005, B = 300;
int n, d, ans;
vector<int> dt[N], adj[N], tmp;
void sol1 (int C) {
  dt[C].push_back(d);
  int S = 1;
  for(auto &T : adj[C]) {
    sol1(T);
    int M = 0; tmp.clear();
    for(int i=0;i<dt[T].size();i++) {
      int D1 = dt[T][i] + 1;
      if(D1 >= d) M = max(M, i);
      for(int j=0;j<dt[C].size();j++) {
        int D2 = dt[C][j];
        if(D1 + D2 >= d) {
          int V = min(D1, D2);
          if(tmp.size() <= i+j) tmp.push_back(V);
          else tmp[i+j] = max(tmp[i+j], min(D1, D2));
        }
      }
    }
    for(int i=0;i<tmp.size();i++) {
      if(dt[C].size() <= i) dt[C].push_back(tmp[i]);
      else dt[C][i] = max(dt[C][i], tmp[i]);
    }
    S += M;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

catinatree.cpp: In function 'void sol1(int)':
catinatree.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dt[T].size();i++) {
               ~^~~~~~~~~~~~~
catinatree.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<dt[C].size();j++) {
                ~^~~~~~~~~~~~~
catinatree.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(tmp.size() <= i+j) tmp.push_back(V);
         ~~~~~~~~~~~^~~~~~
catinatree.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<tmp.size();i++) {
               ~^~~~~~~~~~~
catinatree.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(dt[C].size() <= i) dt[C].push_back(tmp[i]);
       ~~~~~~~~~~~~~^~~~
catinatree.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(dt[C].size() <= S) dt[C].push_back(0);
     ~~~~~~~~~~~~~^~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&d);
  ~~~~~^~~~~~~~~~~~~~
catinatree.cpp:62:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int T; scanf("%d",&T);
          ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49