Submission #1140109


Source Code Expand

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define TRACE(x) cerr << #x << " = " << x << endl
#define REP(i, n) for (int i=0; i<n; i++)
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define _ << " " <<

typedef long long ll;
typedef pair<int, int> P;
#define X first
#define Y second

const int MAX = 1<<18;

int dist_down[MAX], dist_up[MAX];
vector <int> V[MAX];
vector <int> Ld[MAX], Rd[MAX];
int poz_par[MAX], par[MAX];
char s[MAX];

void dfs_down(int node, int pr)
{
  par[node] = pr;
  for (auto it = V[node].begin(); it != V[node].end(); it++)
    if (*it == pr) {
      V[node].erase(it);
      break;
    }

  Ld[node].push_back(0);  
  for (auto it : V[node]) {
    dfs_down(it, node);
    poz_par[it] = (int) Ld[node].size();
    Ld[node].push_back(max(Ld[node].back(), dist_down[it] + 1));
  }
  dist_down[node] = Ld[node].back();

  Rd[node].push_back(0);
  for (int i=(int) V[node].size()-1; i>=0; i--) {
    int it = V[node][i];
    Rd[node].push_back(max(Rd[node].back(), dist_down[it] + 1));
  }

  reverse(Rd[node].begin(), Rd[node].end());    
}

P presjek(P a, P b)
{
  return P(max(a.X, b.X), min(a.Y, b.Y));
}

P unija(P a, P b)
{
  if (a.X > a.Y) return b;
  if (b.X > b.Y) return a;
  P tmp = presjek(a, b);
  assert(tmp.X - 1 <= tmp.Y);
  return P(min(a.X, b.X), max(a.Y, b.Y));
}

P razlika(P a, P b)
{
  P tmp = presjek(a, b);
  if (tmp.X > tmp.Y) return a;
  assert(tmp.Y == a.Y || tmp.X == a.X);
  if (tmp.Y == a.Y) return P(a.X, tmp.X - 1);
  return P(tmp.Y + 1, a.Y);
}

P un[MAX];

ll rje = 0;
void dfs_up(int node, int pr)
{  
  if (pr != -1) {
    dist_up[node] = 1 + max(dist_up[pr],
			    max(Ld[pr][poz_par[node]-1], Rd[pr][poz_par[node]]));
  }    

  //  if (node+1 == 6)
    //    printf("UNPAR %d %d\n", un[pr].X, un[pr].Y);

  if (pr != -1) {
    if (dist_down[node] > dist_up[node] - 1) {
      P tmp = presjek(P(dist_up[node], MAX), P(un[pr].X-1, un[pr].Y-1));

      //      if (node+1 == 5) TRACE(tmp.X _ tmp.Y);
      un[node] = unija(un[node], tmp);
      //      un[pr] = unija(un[pr], P(tmp.X+1, tmp.Y+1));
      //      un[node] = unija(un[node], presjek(P(dust_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
      //      un[pr] = unija(un[pr], presjek(P_P(un[node].X+1, un[node].Y+1));
    }
    //      pres = razlika(pres, presjek(P(dist_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
    else if (dist_down[node] < dist_up[node] - 1) {
      P tmp = presjek(P(dist_down[node] + 2, MAX), P(un[pr].X+1, un[pr].Y+1));

      //if (node+1 == 5) { printf("AA\n"); TRACE(tmp.X _ tmp.Y); }
      un[node] = unija(un[node], tmp);
      //      un[pr] = unija(un[pr], P(tmp.X-1, tmp.Y-1));
      //      un[node] = unija(un[node], P(un[pr].X+1, un[pr].Y+1));
      //      un[pr] = unija(un[pr], P(un[node].X-1, un[node].Y-1));
    }
    //      pres = razlika(pres, presjek(P(dist_down[node] + 2, MAX), P(un[pr].X+1, un[pr].Y+1)));
  }

  P pres = P(0, max(dist_down[node], dist_up[node]) - 1);  
  pres = razlika(pres, un[node]);
  
  //  if (node+1 == 2)
  //    printf("UN %d    %d %d\n", node+1, un[node].X, un[node].Y);


  if (s[node] == '1') {
    un[node] = unija(un[node], pres);
    rje += max(0, pres.Y - pres.X + 1);
    //    printf("NODE %d %d %d\n", node+1, pres.X, pres.Y);
  }

  // if (pr != -1) {
  //   if (dist_down[node] > dist_up[node] - 1)
  //     pres = presjek(pres, P(0, dist_up[node] - 1));
  //   else if (dist_down[node] < dist_up[node] - 1)
  //     pres = presjek(pres, P(0, dist_down[node] + 1));
  // }
  
  //  TRACE(node+1 _ dist_down[node] _ dist_up[node]);
  //TRACE(node+1 _ pres.X _ pres.Y);

  //  printf("UNIJA %d   %d %d\n", node+1, un[node].X, un[node].Y);

  for (auto it : V[node])
    dfs_up(it, node);

  if (pr != -1) {
    if (dist_down[node] > dist_up[node] - 1) {
      P tmp = presjek(P(dist_up[node], MAX), un[node]);

      //      if (node+1 == 5) TRACE(tmp.X _ tmp.Y);
      //      un[node] = unija(un[node], tmp);
      un[pr] = unija(un[pr], P(tmp.X+1, tmp.Y+1));
      //      un[pr] = unija(un[pr], P(tmp.X+1, tmp.Y+1));
      //      un[node] = unija(un[node], presjek(P(dust_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
      //      un[pr] = unija(un[pr], presjek(P_P(un[node].X+1, un[node].Y+1));
    }
    //      pres = razlika(pres, presjek(P(dist_up[node], MAX), P(un[pr].X-1, un[pr].Y-1)));
    else if (dist_down[node] < dist_up[node] - 1) {
      P tmp = presjek(P(dist_down[node] + 2, MAX), un[node]);

      un[pr] = unija(un[pr], P(tmp.X-1, tmp.Y-1));

      //      if (node+1 == 5) { printf("AA\n"); TRACE(tmp.X _ tmp.Y); }
      //      un[node] = unija(un[node], tmp);
      //      un[pr] = unija(un[pr], P(tmp.X-1, tmp.Y-1));
      //      un[node] = unija(un[node], P(un[pr].X+1, un[pr].Y+1));
      //      un[pr] = unija(un[pr], P(un[node].X-1, un[node].Y-1));
    }
    //      pres = razlika(pres, presjek(P(dist_down[node] + 2, MAX), P(un[pr].X+1, un[pr].Y+1)));
  }
}

int main()
{
  REP(i, MAX) un[i] = P(0, -1);
  
  int n;
  scanf("%d", &n);
  REP(i, n-1) {
    int a, b;
    scanf("%d%d", &a, &b); a--; b--;
    V[a].push_back(b);
    V[b].push_back(a);
  }

  scanf(" %s", s);

  dfs_down(0, -1);
  dfs_up(0, -1);

  rje++;
  printf("%lld\n", rje);  
  
  return 0;
}

Submission Info

Submission Time
Task F - Black Radius
User dbradac
Language C++14 (GCC 5.4.1)
Score 1900
Code Size 5494 Byte
Status AC
Exec Time 234 ms
Memory 60288 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:173:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:176:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &a, &b); a--; b--;
                          ^
./Main.cpp:181:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s", s);
                  ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 1300 / 1300 600 / 600
Status
AC × 3
AC × 31
AC × 81
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
Subtask 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt, 2_44.txt, 2_45.txt, 2_46.txt, 2_47.txt
Case Name Status Exec Time Memory
0_00.txt AC 8 ms 24832 KB
0_01.txt AC 8 ms 24832 KB
0_02.txt AC 8 ms 24832 KB
1_00.txt AC 9 ms 24832 KB
1_01.txt AC 223 ms 60288 KB
1_02.txt AC 223 ms 54272 KB
1_03.txt AC 195 ms 43648 KB
1_04.txt AC 181 ms 45176 KB
1_05.txt AC 143 ms 46708 KB
1_06.txt AC 194 ms 44288 KB
1_07.txt AC 194 ms 44288 KB
1_08.txt AC 200 ms 45568 KB
1_09.txt AC 220 ms 52096 KB
1_10.txt AC 210 ms 50688 KB
1_11.txt AC 217 ms 59904 KB
1_12.txt AC 206 ms 47232 KB
1_13.txt AC 221 ms 51328 KB
1_14.txt AC 194 ms 47232 KB
1_15.txt AC 199 ms 45824 KB
1_16.txt AC 207 ms 48384 KB
1_17.txt AC 221 ms 50176 KB
1_18.txt AC 192 ms 43648 KB
1_19.txt AC 190 ms 43904 KB
1_20.txt AC 195 ms 43648 KB
1_21.txt AC 198 ms 44800 KB
1_22.txt AC 183 ms 44668 KB
1_23.txt AC 189 ms 44284 KB
1_24.txt AC 220 ms 45312 KB
1_25.txt AC 190 ms 47480 KB
1_26.txt AC 175 ms 44028 KB
1_27.txt AC 174 ms 45304 KB
1_28.txt AC 160 ms 45944 KB
1_29.txt AC 190 ms 48124 KB
2_00.txt AC 8 ms 24832 KB
2_01.txt AC 218 ms 59520 KB
2_02.txt AC 219 ms 56960 KB
2_03.txt AC 230 ms 56192 KB
2_04.txt AC 217 ms 51712 KB
2_05.txt AC 234 ms 51840 KB
2_06.txt AC 218 ms 53120 KB
2_07.txt AC 194 ms 43648 KB
2_08.txt AC 214 ms 43648 KB
2_09.txt AC 188 ms 43648 KB
2_10.txt AC 171 ms 45176 KB
2_11.txt AC 177 ms 45176 KB
2_12.txt AC 170 ms 45176 KB
2_13.txt AC 139 ms 46708 KB
2_14.txt AC 136 ms 46708 KB
2_15.txt AC 138 ms 46708 KB
2_16.txt AC 187 ms 44288 KB
2_17.txt AC 186 ms 44288 KB
2_18.txt AC 194 ms 44288 KB
2_19.txt AC 185 ms 44288 KB
2_20.txt AC 195 ms 44288 KB
2_21.txt AC 216 ms 44288 KB
2_22.txt AC 205 ms 45440 KB
2_23.txt AC 203 ms 46208 KB
2_24.txt AC 223 ms 45952 KB
2_25.txt AC 212 ms 52608 KB
2_26.txt AC 215 ms 50944 KB
2_27.txt AC 218 ms 52608 KB
2_28.txt AC 201 ms 50304 KB
2_29.txt AC 226 ms 57472 KB
2_30.txt AC 204 ms 55296 KB
2_31.txt AC 211 ms 50304 KB
2_32.txt AC 197 ms 44672 KB
2_33.txt AC 192 ms 47488 KB
2_34.txt AC 196 ms 49664 KB
2_35.txt AC 207 ms 53248 KB
2_36.txt AC 200 ms 43520 KB
2_37.txt AC 189 ms 43776 KB
2_38.txt AC 193 ms 45440 KB
2_39.txt AC 188 ms 43776 KB
2_40.txt AC 178 ms 45048 KB
2_41.txt AC 187 ms 44288 KB
2_42.txt AC 173 ms 44792 KB
2_43.txt AC 233 ms 51968 KB
2_44.txt AC 161 ms 45176 KB
2_45.txt AC 148 ms 46328 KB
2_46.txt AC 147 ms 46708 KB
2_47.txt AC 182 ms 49016 KB