제출 #315238

#제출 시각아이디문제언어결과실행 시간메모리
315238shrek12357새로운 문제 (POI13_luk)C++14
30 / 100
1279 ms22776 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <map> #include <set> #include <climits> #include <cmath> #include <fstream> #include <queue> #include <stack> #include <bitset> using namespace std; #define ll long long //cin.tie(0);ios_base::sync_with_stdio(0); const int MAXN = 3 * 1e5 + 5; vector<int> adjList[MAXN]; int par[MAXN]; int n; bool good; void dfs(int src) { for (auto i : adjList[src]) { if (i == par[src]) { continue; } par[i] = src; dfs(i); } } void check(int src, int mid, int val) { val += mid; val -= adjList[src].size(); if (src != 0) { val++; } if (val < 0) { good = false; } for (auto i : adjList[src]) { if (i == par[src]) { continue; } check(i, mid, val); } } int main() { cin >> n; par[0] = 0; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; adjList[a].push_back(b); adjList[b].push_back(a); } dfs(0); int lo = 0, hi = n; while (lo < hi) { int mid = (lo + hi) / 2; good = true; check(0, mid, 0); if (good) { hi = mid; } else { lo = mid + 1; } } cout << lo << endl; }
#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...