| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 315481 | 2020-10-23T01:03:28 Z | Dymo | Dynamite (POI11_dyn) | C++14 | 1898 ms | 42064 KB |
#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=1e9;
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];
ll cnt1[maxn];
void dfs(ll u,ll par1)
{
par[u]=par1;
for (auto to:adj[u])
{
if (to==par1)
continue;
cnt1[u]++;
dfs(to,u);
}
}
bool chk(ll mid)
{
queue<ll> q;
for (int i=1; i<=n; i++)
{
cnt[i]=cnt1[i];
chk1[i]=0;
chk2[i]=0;
cocan[i]=0;
colua[i]=0;
adj1[i].clear();
}
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);
}
dfs(1,0);
ll l=1, h= 1e9;
while (l<=h)
{
ll mid=(l+h)/2;
if (chk(mid))
{
h=mid-1;
}
else
{
l=mid+1;
}
}
cout <<l;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 10 ms | 14464 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 14464 KB | Output is correct |
| 2 | Correct | 10 ms | 14464 KB | Output is correct |
| 3 | Correct | 10 ms | 14464 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 14464 KB | Output is correct |
| 2 | Correct | 11 ms | 14464 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 14592 KB | Output is correct |
| 2 | Correct | 11 ms | 14592 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 27 ms | 15232 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 110 ms | 18248 KB | Output is correct |
| 2 | Correct | 150 ms | 19092 KB | Output is correct |
| 3 | Correct | 145 ms | 19192 KB | Output is correct |
| 4 | Correct | 167 ms | 21368 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 329 ms | 21596 KB | Output is correct |
| 2 | Correct | 235 ms | 21112 KB | Output is correct |
| 3 | Correct | 217 ms | 20600 KB | Output is correct |
| 4 | Correct | 329 ms | 24728 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1153 ms | 28372 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1639 ms | 34700 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1898 ms | 42064 KB | Output is correct |
| 2 | Correct | 1293 ms | 34192 KB | Output is correct |
| 3 | Correct | 1730 ms | 41184 KB | Output is correct |
| 4 | Correct | 369 ms | 35812 KB | Output is correct |