Submission #315481

#	Time	Username	Problem	Language	Result	Execution time	Memory
315481		Dymo	Untitled (POI11_dyn)	C++14	60 / 100	1898 ms	42064 KiB

Main

#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 (stderr)

dyn.cpp: In function 'int main()':
dyn.cpp:198:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  198 |         freopen("girth.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dyn.cpp:199:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  199 |         freopen("girth.ans", "w", stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10