oj.uz

Submission #763288

# Submission time Handle Problem Language Result Execution time Memory
763288 2023-06-22T07:45:35 Z vjudge1 Power Plant (JOI20_power) C++17
0 / 100
 1 ms 2644 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -