제출 #1168369

#제출 시각아이디문제언어결과실행 시간메모리
1168369Faisal_SaqibTriumphal arch (POI13_luk)C++20
100 / 100
358 ms27672 KiB
/* VENI VIDI VICI */ // #pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector","give-no-fuck") #include <bits/stdc++.h> // #include <iostream> // #include <vector> // #include <algorithm> // #include <set> // #include <map> using namespace std; #define fi first #define se second #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define rep(i,x, n) for (int i = (x); i < (n); ++i) #define repr(i,x, n) for (int i = (n) - 1; i >= (x); --i) // #define sum accumulate using i128 = __int128; using ll = long long; using ull = unsigned long long; using ld = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vpi = vector<pair<int, int>>; using vvi = vector<vi>; template<class T> istream& operator>>(istream& is, vector<T>& v) { for(auto &i:v) is>>i; return is; } template<class T1,class T2> istream& operator>>(istream& is, pair<T1,T2>& p) { is>>p.fi>>p.se; return is; } template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { for(const auto &i:v) os<<i<<' '; return os; } template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& p) { os<<p.fi<<' '<<p.se; return os; } void pyn(bool x) { cout<<(x?"YES":"NO")<<endl; } void pYN(bool x) { cout<<(x?"Yes":"No")<<endl; } void pAB(bool x) { cout<<(x?"Alice":"Bob")<<endl; } ll powmod(ll a,ll b,ll modulo) { if(b==0){ return 1; } ll temp=powmod(a,b/2,modulo); if(b%2==0){ return (temp*temp)%modulo; } else{ return (a*((temp*temp)%modulo))%modulo; } } bool Prime(ll n){ for (ll i = 2; i*i <= n; i++) if (n % i == 0) return false; return (n>1); } const ll N=3e5+100; vl ma[N]; ll dp[N]; void dfs(int x,int p=-1,int vl=1) { dp[x]=vl-ma[x].size()+(p!=-1); for(auto y:ma[x]) { if(y==p)continue; dfs(y,x,vl); dp[x]+=min(dp[y],0ll); } } bool check(ll x) { dfs(1,-1,x); return dp[1]>=0; } void solve() { ll n; cin>>n; rep(i,1,n) { int x,y; cin>>x>>y; ma[x].pb(y); ma[y].pb(x); } ll l=-1,r=n; // zero can be answer while(l+1<r) { ll mid=(l+r)/2; if(check(mid)) { r=mid; } else { l=mid; } } cout<<r<<endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int uwu=1; // cin>>uwu; while(uwu--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...