Submission #315672

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
315672	2020-10-23T15:56:17 Z	Dymo	Dynamite (POI11_dyn)	C++14	100 / 100	2368 ms	43448 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=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);
            // cout <<i<<endl;
        }
    }
    ll ans=0;
    while (!q.empty())
    {
        auto p=q.front();
        q.pop();
        bool chklua=false;
        bool chkcan=false;
        ll solua=0;
        ll socan=0;
        /*4 1
1 1 1 0
2 3
3 4
1 3*/
        while (1)
        {
           // cout <<p<<endl;
            if (chkcan==true)
            {
                socan++;
                /*if (p==1)
                {
                    cout <<"WTF"<<endl;
                }*/
            }
            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)
            {
               /* if (p==1)
                {
                    cout <<"WTF"<<endl;
                }*/
                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 (p==1)
             {
                  cout <<cocan[p]<<" "<<chk2[p]<<" "<<colua[p]<<" "<<chk1[p]<<" "<<p<<" "<<chkcan<<" "<<socan<<endl;
             }*/
            if (chkcan&&socan==mid)
            {
                chklua=true;
                solua=mid;
                //cout <<p<<endl;
                ans++;
              //  cout <<p<<endl;
                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;
                   // cout <<p<<" "<<to<<" "<<colua[p]<<endl;
                    ans++;
                    socan=false;
                    chkcan=false;
                }

                chk1[p]=chklua;
                chk2[p]=chkcan;
                colua[p]=solua;
                cocan[p]=socan;
               // cout <<to<<" "<<p<<"ok"<<" "<<chk2[p]<<" "<<chkcan<<endl;
                 // if (p==3)   cout <<chk2[p]<<" "<<chkcan<<endl;

            }

           /*  if (p==3)
             {
                  cout <<cocan[p]<<" "<<chk2[p]<<" "<<colua[p]<<" "<<chk1[p]<<" "<<par[p]<<" "<<chkcan<<endl;
             }*/
            if (par[p]==-1)
                break;
            cnt[par[p]]--;
            if (cnt[par[p]])
            {
                adj1[par[p]].pb(p);
                  break;
            }
             //cout <<p<<"nxt"<<endl;
            p=par[p];
        }
    }
   for (int i=1; i<=n; i++)
    {
      //  cout <<cocan[i]<<" "<<chk2[i]<<" "<<colua[i]<<" "<<chk1[i]<<" "<<i<<endl;
    }
   // cout <<ans<<endl;
//  cout <<colua[3]<<" "<<cocan[3]<<" "<<chk1[3]<<" "<<chk2[3]<<endl;
    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;
   // cout <<chk(1);
    /* 6
    1
    0 0 0 0 1 1
    1 2
    2 3
    2 4
    3 5
    4 6*/
    /*6
    1
    0 0 0 0 1 1
    1 2
    2 3
    2 4
    3 5
    3 6*/


}

Compilation message

dyn.cpp:13:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+9' to '2147483647' [-Woverflow]
   13 | const ll base=3e9;
      |               ^~~
dyn.cpp: In function 'int main()':
dyn.cpp:235:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  235 |         freopen("girth.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dyn.cpp:236:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  236 |         freopen("girth.ans", "w", stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	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
4	Correct	10 ms	14464 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	14464 KB	Output is correct
2	Correct	11 ms	14464 KB	Output is correct
3	Correct	10 ms	14464 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	14464 KB	Output is correct
2	Correct	10 ms	14464 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	14592 KB	Output is correct
2	Correct	11 ms	14592 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	15136 KB	Output is correct
2	Correct	44 ms	15744 KB	Output is correct
3	Correct	63 ms	16632 KB	Output is correct
4	Correct	58 ms	17144 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	114 ms	17944 KB	Output is correct
2	Correct	181 ms	18808 KB	Output is correct
3	Correct	276 ms	18808 KB	Output is correct
4	Correct	260 ms	20984 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	359 ms	21052 KB	Output is correct
2	Correct	318 ms	20728 KB	Output is correct
3	Correct	400 ms	20008 KB	Output is correct
4	Correct	520 ms	24160 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1212 ms	27636 KB	Output is correct
2	Correct	1126 ms	28768 KB	Output is correct
3	Correct	1818 ms	35128 KB	Output is correct
4	Correct	1826 ms	35644 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2368 ms	33608 KB	Output is correct
2	Correct	1694 ms	37436 KB	Output is correct
3	Correct	2128 ms	38776 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2225 ms	40764 KB	Output is correct
2	Correct	1690 ms	36560 KB	Output is correct
3	Correct	2357 ms	43448 KB	Output is correct
4	Correct	507 ms	39268 KB	Output is correct