Submission #763288

#	Time	Username	Problem	Language	Result	Execution time	Memory
763288		vjudge1	Power Plant (JOI20_power)	C++17	0 / 100	1 ms	2644 KiB

power

#include<bits/stdc++.h>
using namespace std;

int n, x, y, ans = 0;
pair<int, int> cnt[100001];
vector<int> vec[100001];
string s;
bool visited[100001];

void dfs(int x, bool ok)
{
	visited[x] = true;
	if(s[x - 1] == '1' && x != cnt[n].second)
	{
		ok = 1;
		++ans;
		return;
	}
	for(int c : vec[x])
	{
		if(!visited[c])
		{
			dfs(c, ok);
		}
		if(x == cnt[n].second)	ok = 0;
		if(ok)	return;
	}
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cnt[i] = {0, 0};
	}
	for(int i = 1; i < n; ++i)
	{
		cin >> x >> y;
		++cnt[x].first;	++cnt[y].first;
		cnt[x].second = x;	cnt[y].second = y;
		vec[x].push_back(y);	vec[y].push_back(x);
	}
	sort(cnt + 1, cnt + n + 1);
	cin >> s;
	dfs(cnt[n].second, 0);
	cout << ans - s[n - 1] + '0';
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53