Submission #1168335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168335		hynmj	Triumphal arch (POI13_luk)	C++20	20 / 100	2094 ms	37892 KiB

luk

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
// #define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define vb vector<bool>
#define vv vector<vi>
#define vp vector<pi>
#define ul map<int,vi>
#define ub map<int,bool>
#define ui map<int,int>
#define sum(a) accumulate(all(a),0)
#define add insert
#define endl '\n' 
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
ul graph;
const int N = 2e5+7;
int u,v,n,k,m,e,w;
int a[N];
int dep[N];
int cnt[N];
int ans=0;
bool yes;
int pcnt[N];
int ncnt[N];
int x;
void dfs(int node,int parent)
{
    if (node !=1)
    {
        cnt [node] += +cnt [parent];
        cnt [node] += x-(ll)graph[parent].size()+1;
    }
    // ln;
    // cout << "node = "<< node << endl;
    // rep(10)cout << cnt[i]<< " ";
    for(int i:graph[node])
    {
        if(i==parent)continue;
        ans = max(ans, (ll)graph[i].size()-1);
        dfs(i,node);
        cnt [node]+= min(cnt[i],0ll);
    }
    if (cnt[node]<0)
    {
        yes=0;
    }
    
}


bool f()
{
    // return 0;
    yes =1;
    rep(n+3)cnt [i]=0;
    dfs(1,0);
    // rep(10)cout << cnt[i]<< " ";
    return yes;
}
void solve()
{
    yes = 0; 
    // graph.clear();
    cin>>n;
    // rep(n){cin>>e;a.append(e);}
    rep(n-1)
    {
        cin>>u>>v;
        graph[u].append(v);
        graph[v].append(u);
    }
    int l=0,r=n+1;
    while (r-l>1)
    {
        int mid=(r+l)/2;
        x=mid;
        if (f())
        {
            r=mid;
        }
        else l=mid;
    }
    cout << r;
    // x= 1 ;
    // cout << f();
    // cout << r;
    // for (auto i: a){cout<<i<<" ";}
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    while(ans--){
        // cout << "Case #" << ans << ": \n";
        solve();ln;}}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 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