Submission #317200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
317200	2020-10-29T05:24:23 Z	casperwang	Balanced Tree (info1cup18_balancedtree)	C++14	Compilation error	0 ms	0 KB

balancedtree

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

void DFS(int now, int par, int d0, int d1, vector <int> &dp0, vector <int> &dp1, vector <int> &c, vector<vector<int>> &path, vector<vector<int>> &p2) {
  if (par) p2[now].pb(par);
  dp0[now] = min(dp0[now], d0);
  dp1[now] = min(dp1[now], d1);
  for (int i : path[now]) {
    if (i == par) continue;
    deg[i]--;
    if (deg[i] <= 1) {
      if (c[now])
        DFS(i, now, 1, dp1[now]+1, c, path, p2);
      else
        DFS(i, now, dp0[now]+1, 1, c, path, p2);
    }
  }
}

dfs(int now, int par, vector<int> &dp0, vector<int> &dp1, vector<vector<int>> &p2) {
  for (int i : p2[now]) {
    dp0[i] = min(dp0[i], dp0[now]+1);
    dp1[i] = min(dp1[i], dp1[now]+1);
    dfs(i, now, dp0, dp1, p2);
  }
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector <vector<int>> path(n+1), p2(n+1);
    vector <int> deg(n+1), dp0(n+1), dp1(n+1);
    for (int i = 1; i <= n; i++)
      dp0[i] = dp1[i] = n+1;
    int a, b;
    for (int i = 1; i < n; i++) {
      cin >> a >> b;
      path[a].pb(b);
      deg[a]++;
      path[b].pb(a);
      deg[b]++;
    }
    vector <bool> tf(n+1);
    vector <int> c(n+1);
    for (int i = 1; i <= n; i++)
      cin >> c[i];
    int ans = 1;
    for (int i = 1; i <= n; i++)
      if (deg[i] == 1) DFS(i, 0, n+1, n+1, dp0, dp1, c, path, p2);
    for (int i = 1; i <= n; i++)
      for (int j : p2[i]) tf[j] = 1;
    for (int i = 1; i <= n; i++)
      if (!tf[i]) dfs(i, 0, dp0, dp1, p2);
    for (int i = 1; i <= n; i++)
      ans = max({ans, dp0[i], dp1[i]});
    if (ans > n) cout << -1 << "\n";
    else cout << ans << "\n";
  }
}

Compilation message

balancedtree.cpp: In function 'void DFS(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
balancedtree.cpp:14:5: error: 'deg' was not declared in this scope
   14 |     deg[i]--;
      |     ^~~
balancedtree.cpp:17:39: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<std::vector<int> >'
   17 |         DFS(i, now, 1, dp1[now]+1, c, path, p2);
      |                                       ^~~~
balancedtree.cpp:8:77: note: in passing argument 6 of 'void DFS(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)'
    8 | void DFS(int now, int par, int d0, int d1, vector <int> &dp0, vector <int> &dp1, vector <int> &c, vector<vector<int>> &path, vector<vector<int>> &p2) {
      |                                                               ~~~~~~~~~~~~~~^~~
balancedtree.cpp:19:39: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<std::vector<int> >'
   19 |         DFS(i, now, dp0[now]+1, 1, c, path, p2);
      |                                       ^~~~
balancedtree.cpp:8:77: note: in passing argument 6 of 'void DFS(int, int, int, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)'
    8 | void DFS(int now, int par, int d0, int d1, vector <int> &dp0, vector <int> &dp1, vector <int> &c, vector<vector<int>> &path, vector<vector<int>> &p2) {
      |                                                               ~~~~~~~~~~~~~~^~~
balancedtree.cpp: At global scope:
balancedtree.cpp:24:82: error: ISO C++ forbids declaration of 'dfs' with no type [-fpermissive]
   24 | dfs(int now, int par, vector<int> &dp0, vector<int> &dp1, vector<vector<int>> &p2) {
      |                                                                                  ^
balancedtree.cpp: In function 'int dfs(int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&)':
balancedtree.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
   30 | }
      | ^