This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
const int N = 222222;
int n, q, v0;
vector<ll> g[N];
string s, c;
bool boo;
bool used[N];
void dfs(int v, int p, int w)
{
used[v] = 1;
if (v == w)
{
boo = 0;
for (int i=1; i<=n; i++)
if (used[i] && v0 != i && i != w && c[i-1] == '1')
{
q--, c[i-1] = '0';
}
}
for (auto l:g[v])
if (l != p && boo) dfs(l, v, w);
used[v] = 0;
}
int main()
{
cin >> n;
for (int i=1,x,y; i<n; i++)
{
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
cin >> s;
vector<int> v;
int ans = 0;
for (int k=0; k<64; k++)
{
q = 0;
v.clear();
c = s;
for (int i=0; i<n; i++)
if (s[i] == '1' && k & (1 << i)) q++, v.push_back(i+1);
for (int i=0; i<v.size(); i++)
for (int j=i+1; j<v.size(); j++)
{
boo = 1;
v0 = v[i];
memset(used, 0, sizeof(used));
dfs(v[i], 0, v[j]);
}
ans = max(ans, q);
}
cout << ans;
return 0;
}
Compilation message (stderr)
power.cpp: In function 'int main()':
power.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i=0; i<v.size(); i++)
| ~^~~~~~~~~
power.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int j=i+1; j<v.size(); j++)
| ~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |