oj.uz

Submission #315474

# Submission time Handle Problem Language Result Execution time Memory
315474 2020-10-23T00:55:43 Z Dymo Dynamite (POI11_dyn) C++14
70 / 100
 2289 ms 44180 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);
        }
    }
    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

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: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
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 14496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 10 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 11 ms 14464 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 15104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 18024 KB Output is correct
2 Correct 181 ms 18892 KB Output is correct
3 Correct 276 ms 18936 KB Output is correct
4 Correct 255 ms 21036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 21244 KB Output is correct
2 Correct 295 ms 20624 KB Output is correct
3 Correct 380 ms 19960 KB Output is correct
4 Correct 490 ms 24072 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1190 ms 27636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2153 ms 33468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2187 ms 40648 KB Output is correct
2 Correct 1627 ms 37392 KB Output is correct
3 Correct 2289 ms 44180 KB Output is correct
4 Correct 493 ms 40504 KB Output is correct