Submission #1013872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013872		vjudge1	Triumphal arch (POI13_luk)	C++17	0 / 100	133 ms	35332 KiB

luk

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
// #define int long long
#define mod 1000000007
#define base 200003
#define base2 7001
// #define pi acos(-1)
#define double long double
// #define ordered_set tree<pair<int, int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")
 
constexpr int maxn = 1000001;
const int N = 1 << (int)(ceil(log2(maxn)));
 
int n, depth[maxn], freq[maxn];
vector<int> adj[maxn];
bool vis[maxn];

void dfs(int i, int cnt)
{
    vis[i] = 1;
    depth[i] = cnt;
    for (auto j : adj[i])
    {
        if (!vis[j])
            dfs(j, cnt + 1);
    }
    return;
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs (1, 0);
    for (int i = 2; i <= n; i++)
        freq[depth[i]]++;

    vector<int>v;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!freq[i])
            break;
        v.push_back(freq[i]);
        mx = max(mx, freq[i]);
    }

    int l = 0, r = 3e5 + 5;
    int ans = -1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        int x = 0;
        bool flag = 1;
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i] - m - x > 0)
            {
                flag = 0;
                break;
            }
            x = (m + x) - v[i];
        }
        if (flag)
        {
            r = m - 1;
            ans = m;
        }
        else
            l = m + 1;
    }
    cout << ans;
}

Compilation message (stderr)

luk.cpp: In function 'int main()':
luk.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < v.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