Submission #1013855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013855		vjudge1	Triumphal arch (POI13_luk)	C++17	0 / 100	129 ms	23468 KiB

luk

//B - Triumphal arch


#include <bits/stdc++.h>
//#define endl '\n'
#define mod 1000000007

using namespace std;
vector<vector<long long>> v(300003);
long long depth[300003], n, nu=0;
bool vis[300003];
void dfs(long long x, long long dep=0)
{
    nu=max(nu, dep);
    depth[dep]++;
    vis[x]=1;
    for(long long i=0; i<v[x].size(); i++)
    {
        long long y=v[x][i];
        if(!vis[y])
            dfs(y, dep+1);
    }
}

long long check(long long x)
{
    long long y=0, yo=0;
    for(long long i=1; i<=n; i++)
    {
        yo++;
        y+=x;
        y-=depth[i];
        if(y<0)
        {
            y*=-1;
            if(y%yo==0) x+=y/yo;
            else    x+=(y+yo)/yo;
            y-=yo;
        }
    }
    return x;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin>>n;
    if(n==1)
        cout<<0<<endl;
    else
    {
        for(long long i=1; i<n; i++)
        {
            long long a,b;
            cin>>a>>b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        dfs(1);
        cout<<check((n-1)/nu)<<endl;
    }
    return 0;
}

Compilation message (stderr)

luk.cpp: In function 'void dfs(long long int, long long int)':
luk.cpp:17:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(long long i=0; i<v[x].size(); i++)
      |                        ~^~~~~~~~~~~~

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