oj.uz

Submission #28746

# Submission time Handle Problem Language Result Execution time Memory
28746 2017-07-16T12:50:05 Z samir_droubi Torrent (COI16_torrent) C++14
100 / 100
 239 ms 35172 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
const int mxn=(3e5)+5;
int a,b;
vector<int>tr[mxn];
int dep[mxn];
int pa[mxn];
bool path[mxn];
void dfs(int v,int p)
{
    for(int i=0;i<tr[v].size();++i)
    {
        int u=tr[v][i];
        if(u==p)continue;
        dep[u]=dep[v]+1;
        pa[u]=v;
        dfs(u,v);
    }
}
void lca()
{
    int x=a;
    int y=b;
    path[x]=true;
    path[y]=true;

    if(dep[x]>dep[y])swap(y,x);
    while(dep[y]!=dep[x])
    {
        y=pa[y];
        path[y]=true;
    }
    if(x==y)return;

    while(pa[x]!=pa[y])
    {
        x=pa[x];
        y=pa[y];
        path[x]=true;
        path[y]=true;
    }
    path[pa[x]]=true;
}

int dp[mxn];
bool cmp(int x,int y)
{
    return dp[x]>dp[y];
}
void dfs1(int v,int p)
{
    dp[v]=0;    
    for(int i=0;i<tr[v].size();++i)
    {
        int u=tr[v][i];
        if(u==p||path[u])continue;
        dfs1(u,v);
    }
    sort(tr[v].begin(),tr[v].end(),cmp);
    int c=0;
    for(int i=0;i<tr[v].size();++i)
    {
        int u=tr[v][i];
        if(u==p||path[u])continue;
        ++c;
        dp[u]+=c;
        dp[v]=max(dp[v],dp[u]);
    }
}

vector<int>vv[mxn];
bool explored[mxn];
bool check(int T)
{
    memset(explored,0,sizeof explored);
    for(int i=0;i<mxn;++i)vv[i].clear();
    vv[0].push_back(a);
    vv[0].push_back(b);
    for(int i=0;i<T;++i)
    {
        for(int j=0;j<vv[i].size();++j)
        {
            int v=vv[i][j];
            if(explored[v])continue;
            explored[v]=true;
            if(dp[v]+i>T)return false;
            int del=1;
            int node=-1;
            for(int k=0;k<tr[v].size();++k)
            {
                int u=tr[v][k];
                if(path[u])
                {
                    if(!explored[u])node=u;
                    continue;
                }
                if(dp[u]+i==T)++del;
            }
            if(node==-1)continue;
            if(del+i>=T)continue;
            vv[del+i].push_back(node);
        }
    }
    bool ok=true;
    for(int i=1;i<=n;++i)
        if(path[i]&&!explored[i])ok=false;
    return ok;
}
void bs()
{
    int l=1;
    int r=n;
    int ans=-1;
    while(l<=r)
    {
        int md=(l+r)/2;
        if(check(md))
        {
            ans=md;
            r=md-1;
        }
        else l=md+1;
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=0;i<n-1;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        tr[x].push_back(y);
        tr[y].push_back(x);
    }

    dfs(1,1);
    lca();

    for(int i=1;i<=n;++i)
    {
        if(!path[i])continue;
        dfs1(i,i);
    }

    bs();
}

Compilation message

torrent.cpp: In function 'void dfs(int, int)':
torrent.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();++i)
                  ^
torrent.cpp: In function 'void dfs1(int, int)':
torrent.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();++i)
                  ^
torrent.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tr[v].size();++i)
                  ^
torrent.cpp: In function 'bool check(int)':
torrent.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<vv[i].size();++j)
                      ^
torrent.cpp:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<tr[v].size();++k)
                          ^
torrent.cpp: In function 'int main()':
torrent.cpp:129:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&a,&b);
                             ^
torrent.cpp:133:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20188 KB Output is correct
2 Correct 6 ms 20188 KB Output is correct
3 Correct 6 ms 20188 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 32216 KB Output is correct
2 Correct 216 ms 33880 KB Output is correct
3 Correct 239 ms 33960 KB Output is correct
4 Correct 169 ms 34884 KB Output is correct
5 Correct 223 ms 31796 KB Output is correct
6 Correct 209 ms 32064 KB Output is correct
7 Correct 196 ms 35172 KB Output is correct