# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
315474 | Dymo | Untitled (POI11_dyn) | C++14 | 2289 ms | 44180 KiB |
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>
using namespace std;
#define pb push_back
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=3e5+100;
const ll mod =1e9 + 7 ;
const ll base=3e9;
ll nw[maxn];
ll a[maxn];
ll cnt[maxn];
ll par[maxn];
ll n, m;
ll cocan[maxn];
ll colua[maxn];
bool chk1[maxn];
bool chk2[maxn];
vector<ll> adj[maxn];
vector<ll> adj1[maxn];
void dfs(ll u,ll par1)
{
par[u]=par1;
for (auto to:adj[u])
{
if (to==par1)
continue;
cnt[u]++;
dfs(to,u);
}
}
bool chk(ll mid)
{
queue<ll> q;
for (int i=1; i<=n; i++)
{
cnt[i]=0;
chk1[i]=0;
chk2[i]=0;
cocan[i]=0;
colua[i]=0;
adj1[i].clear();
}
dfs(1,0);
for (int i=1; i<=n; i++)
{
if (cnt[i]==0)
{
q.push(i);
}
}
ll ans=0;
while (!q.empty())
{
auto p=q.front();
q.pop();
bool chklua=false;
bool chkcan=false;
ll solua=0;
ll socan=0;
while (1)
{
if (chkcan==true)
{
socan++;
}
if (chklua==true)
{
solua--;
}
if (solua<0)
{
solua=0;
chklua=0;
}
if (chk1[p]==true)
{
chklua=true;
solua=max(solua,colua[p]);
}
if (chk2[p]==true)
{
chkcan=true;
socan=max(socan,cocan[p]);
}
if (a[p])
{
chkcan=true;
socan=max(socan,0);
}
if (chkcan&&chklua)
{
if (solua>=socan)
{
chkcan=false;
socan=0;
}
}
if (chkcan&&socan==mid)
{
chklua=true;
solua=mid;
ans++;
socan=0;
chkcan=0;
}
chk1[p]=chklua;
chk2[p]=chkcan;
colua[p]=solua;
cocan[p]=socan;
for (auto to:adj1[p])
{
chkcan=chk2[to];
chklua=chk1[to];
solua=colua[to];
socan=cocan[to];
if (chkcan==true)
{
socan++;
}
if (chklua==true)
{
solua--;
}
if (solua<0)
{
solua=0;
chklua=0;
}
if (chk1[p]==true)
{
chklua=true;
solua=max(solua,colua[p]);
}
if (chk2[p]==true)
{
chkcan=true;
socan=max(socan,cocan[p]);
}
if (a[p])
{
chkcan=true;
socan=max(socan,0);
}
if (chkcan&&chklua)
{
if (solua>=socan)
{
chkcan=false;
socan=0;
}
}
if (chkcan&&socan==mid)
{
chklua=true;
solua=mid;
ans++;
socan=false;
chkcan=false;
}
chk1[p]=chklua;
chk2[p]=chkcan;
colua[p]=solua;
}
if (par[p]==-1)
break;
cnt[par[p]]--;
if (cnt[par[p]])
{
adj1[par[p]].pb(p);
break;
}
p=par[p];
}
}
ans=ans+chk2[1];
if (ans<=m)
return true;
return false;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("girth.t", "r"))
{
freopen("girth.inp", "r", stdin);
freopen("girth.ans", "w", stdout) ;
}
cin>>n>>m ;
for (int i=1; i<=n; i++)
{
cin>>a[i];
}
for (int i=1; i<=n-1; i++)
{
ll x, y;
cin>>x>> y;
adj[x].pb(y);
adj[y].pb(x);
}
ll l=0, h= n;
while (l<=h)
{
ll mid=(l+h)/2;
if (chk(mid))
{
h=mid-1;
}
else
{
l=mid+1;
}
}
cout <<l;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |