Submission #5559792


Source Code Expand

#pragma GCC optimize ("-O3") 
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  __MAKE_TIME__  Problem: __PROBLEM__ / Link: __CONTEST_URL__  ----- */



template <class N, class E>
struct Rerooting {
	int n;
	const vector<vector<E>>& G;
	vector<N> subtreesum;
	vector<vector<N>> dp; // L
	vector<unordered_map <int, N>>edgememo;
	void dfs1(int v, int p) {
		subtreesum[v] = N();
		for (auto e : G[v]) {
			int nx = e.to;
			if (nx == p) continue;
			dfs1(nx, v);
			subtreesum[v] = subtreesum[v] + subtreesum[nx].include_e(v, e);
		}
		subtreesum[v] = subtreesum[v].include_v(v);
	}
	void dfs2(int v, int p, N top) {
		int deg = int(G[v].size());
		dp[v] = vector<N>(deg + 1);
		dp[v][0] = N();
		for (int i = 0; i < deg; i++) {
			int nx = G[v][i].to;
			dp[v][i + 1] =
				dp[v][i] + (nx == p ? top : subtreesum[nx]).include_e(v, G[v][i]);
		}
		N rnode = N();
		dp[v].back() = dp[v].back().include_v(v);
		for (int i = deg - 1; i >= 0; i--) {
			dp[v][i] = (dp[v][i] + rnode).include_v(v);
			int nx = G[v][i].to;
			edgememo[v][nx] = dp[v][i];
			if (nx != p)dfs2(nx, v, dp[v][i]);
			rnode = rnode + (nx == p ? top : subtreesum[nx]).include_e(v, G[v][i]);
		}
	}
	Rerooting(const vector<vector<E>>& _g, int root) : n(int(_g.size())), G(_g), subtreesum(n), dp(n), edgememo(int(_g.size())) {
		dfs1(root, -1);
		dfs2(root, -1, N());
	}
};

template <class N, class E> vector<vector<N>> Rerooting_get(const vector<vector<E>>& g, int root) {
	return Rerooting<N, E>(g, root).dp;
}

inline int ri() { int in; int y = scanf("%d", &in); return in; }
inline LL ril() { LL in; int y = scanf("%lld", &in); return in; }
inline void oi(LL out) { printf("%lld\n", out); }

int main() {

	struct Edge
	{
		int to;
		Edge(int t) :to(t) {}
	};

	int N = ri();
	vector<vector<Edge>>G(2 * N);
	vector<PII>edge(N - 1);
	FOR(i, 0, N - 1) {
		int a = ri() - 1, b = ri() - 1;
		G[a].push_back(Edge(b));
		G[b].push_back(Edge(a));
		edge[i] = PII(a, b);
	}

	static string s; cin >> s;

	struct Node {
		PLL d;
		int onecnt;
		Node() :d(PLL(0, 0)), onecnt(0) {}
		Node include_e(int, const Edge&) const {
			Node res = *this;
			res.d.second = 0;
			res.d.first++;

			return res;
		}

		Node operator + (const Node& r) const {
			Node res = *this;
			for (auto it : { r.d.first,r.d.second }) {
				if (res.d.first < it) {
					res.d.second = res.d.first;
					res.d.first = it;
				}
				else if (res.d.second < it) {
					res.d.second = it;
				}
			}
			res.onecnt += r.onecnt;
			return res;
		}

		Node include_v(int v) const {
			Node res = *this;
			if (s[v] == '1')res.onecnt++;
			return res;
		}
	};

	auto all_tree = Rerooting<Node, Edge>(G, 0);
	auto tree_dp_v = all_tree.dp;
	auto tree_dp_e = all_tree.edgememo;
	LL ans = 0;

	// vertex c
	FOR(i, 0, N) {
		LL OK = tree_dp_v[i].back().d.second;
		LL DW = INF;
		DD(de(tree_dp_v[i].back().d));
		for (auto it : tree_dp_v[i]) {
			if (it.onecnt)
				DW = min(DW, it.d.first);
		}
		if (s[i] == '1')DW = 0;
		DD(de(OK, DW));
		if (DW <= OK)
			ans += OK - DW + 1;
	}
	DD(de(ans));
	// edge c
	FOR(i, 0, N - 1) {
		int a, b;
		tie(a, b) = edge[i];
		Node d1 = tree_dp_e[a][b];
		Node d2 = tree_dp_e[b][a];
		DD(de(d1.d, d1.onecnt, d2.d, d2.onecnt));
		if (d1.d.first > d2.d.first) {
			ans += d2.onecnt > 0;
		}
		else if (d1.d.first < d2.d.first) {
			ans += d1.onecnt > 0;
		}
		else ans++;

	}
	oi(ans);

	return 0;
}

Submission Info

Submission Time
Task F - Black Radius
User Yang33
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 4428 Byte
Status WA
Exec Time 645 ms
Memory 205572 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 1300 / 1300 0 / 600
Status
AC × 3
AC × 31
AC × 50
WA × 31
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 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 528 ms 205572 KB
1_02.txt AC 532 ms 195460 KB
1_03.txt AC 479 ms 177156 KB
1_04.txt AC 589 ms 177808 KB
1_05.txt AC 541 ms 178712 KB
1_06.txt AC 471 ms 177412 KB
1_07.txt AC 471 ms 177408 KB
1_08.txt AC 478 ms 179588 KB
1_09.txt AC 509 ms 189956 KB
1_10.txt AC 496 ms 185092 KB
1_11.txt AC 525 ms 202116 KB
1_12.txt AC 478 ms 176900 KB
1_13.txt AC 522 ms 188676 KB
1_14.txt AC 493 ms 180356 KB
1_15.txt AC 471 ms 179332 KB
1_16.txt AC 493 ms 183168 KB
1_17.txt AC 520 ms 187652 KB
1_18.txt AC 470 ms 175108 KB
1_19.txt AC 469 ms 175236 KB
1_20.txt AC 479 ms 174468 KB
1_21.txt AC 483 ms 178692 KB
1_22.txt AC 472 ms 176392 KB
1_23.txt AC 468 ms 176524 KB
1_24.txt AC 587 ms 177540 KB
1_25.txt AC 606 ms 181648 KB
1_26.txt AC 452 ms 172552 KB
1_27.txt AC 594 ms 176784 KB
1_28.txt AC 584 ms 178996 KB
1_29.txt AC 487 ms 183200 KB
2_00.txt AC 1 ms 256 KB
2_01.txt AC 536 ms 204420 KB
2_02.txt AC 535 ms 200068 KB
2_03.txt AC 533 ms 198532 KB
2_04.txt AC 533 ms 190852 KB
2_05.txt AC 527 ms 191236 KB
2_06.txt AC 530 ms 195460 KB
2_07.txt AC 492 ms 177156 KB
2_08.txt WA 485 ms 177156 KB
2_09.txt AC 486 ms 177156 KB
2_10.txt AC 601 ms 177808 KB
2_11.txt AC 599 ms 177808 KB
2_12.txt AC 606 ms 177808 KB
2_13.txt AC 550 ms 178712 KB
2_14.txt AC 544 ms 178712 KB
2_15.txt AC 548 ms 178712 KB
2_16.txt WA 470 ms 179460 KB
2_17.txt WA 470 ms 177412 KB
2_18.txt WA 478 ms 177412 KB
2_19.txt WA 473 ms 177412 KB
2_20.txt WA 473 ms 177412 KB
2_21.txt WA 474 ms 177540 KB
2_22.txt WA 481 ms 179332 KB
2_23.txt WA 491 ms 180608 KB
2_24.txt WA 475 ms 180100 KB
2_25.txt AC 504 ms 190852 KB
2_26.txt WA 508 ms 188292 KB
2_27.txt WA 510 ms 190848 KB
2_28.txt WA 495 ms 186112 KB
2_29.txt WA 524 ms 199940 KB
2_30.txt AC 519 ms 194180 KB
2_31.txt WA 518 ms 186756 KB
2_32.txt WA 477 ms 178052 KB
2_33.txt WA 492 ms 181888 KB
2_34.txt WA 488 ms 183556 KB
2_35.txt WA 516 ms 189956 KB
2_36.txt WA 476 ms 175108 KB
2_37.txt WA 476 ms 175620 KB
2_38.txt WA 478 ms 177668 KB
2_39.txt WA 480 ms 176640 KB
2_40.txt WA 602 ms 177552 KB
2_41.txt WA 464 ms 175492 KB
2_42.txt WA 583 ms 174480 KB
2_43.txt WA 645 ms 189316 KB
2_44.txt WA 594 ms 175376 KB
2_45.txt WA 588 ms 178076 KB
2_46.txt WA 576 ms 178328 KB
2_47.txt WA 588 ms 183372 KB