제출 #1119144

#제출 시각아이디문제언어결과실행 시간메모리
1119144quochuy147Torrent (COI16_torrent)C++14
100 / 100
460 ms54540 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define mp make_pair #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define all(x) (x).begin() , (x).end() #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define file "name" template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;} template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;} const int inf = 1e9; const ll linf = 1e17; const int mod = 1e9 + 7; const int N = 1e6 + 5; int n, s, t; int en[2][N]; vector <int> a[N]; vector <int> p; bool check; int res = inf; int f[N]; void inp() { cin >> n >> s >> t; for(int i = 1; i < n; ++i) { int u, v; cin >> u >> v; a[u].pb(v); a[v].pb(u); } } void dfs_pre(int u, int pre) { if(u == t) check = 1; for(int v : a[u]) { if(v == pre || check) continue; dfs_pre(v, u); } if(check) p.pb(u); } int dfs(int u, int pre, bool type) { f[u] = 0; vector <int> x; for(int v : a[u]) { if(v == pre || en[type][v]) continue; x.pb(dfs(v, u, type)); } sort(x.begin(), x.end(), greater <int>()); for(int i = 0; i < x.size(); ++i) maximize(f[u], x[i] + i + 1); return f[u]; } bool cal(int k) { en[1][p[k]] = 1; en[0][p[k + 1]] = 1; int cx = dfs(s, 0, 0); int cy = dfs(t, 0, 1); // cout << cx << ' ' << cy << '\n'; minimize(res, max(cx, cy)); en[1][p[k]] = 0; en[0][p[k + 1]] = 0; return cx <= cy; } void solve() { dfs_pre(s, s); reverse(p.begin(), p.end()); cal(0); int l = 0, r = p.size() - 2, id = 1; while(l <= r) { int m = (l + r) >> 1; if(cal(m)) { l = m + 1; id = m; } else r = m - 1; } if(id + 1 < p.size()) cal(id + 1); cout << res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen(file".inp" , "r" , stdin); // freopen(file".out" , "w" , stdout); inp(); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'int dfs(int, int, bool)':
torrent.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < x.size(); ++i) maximize(f[u], x[i] + i + 1);
      |                    ~~^~~~~~~~~~
torrent.cpp: In function 'void solve()':
torrent.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if(id + 1 < p.size()) cal(id + 1);
      |        ~~~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...