제출 #569578

#제출 시각아이디문제언어결과실행 시간메모리
569578jcelinTorrent (COI16_torrent)C++14
0 / 100
770 ms61464 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; #define ii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vii vector<ii> #define vll vector<ll> #define vpll vector<pll> #define matrix vector<vi> #define matrixLL vector<vLL> #define vs vector<string> #define vui vector<ui> #define msi multiset<int> #define mss multiset<string> #define si set<int> #define ss set<string> #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define FOR(i, a, b) for (int i = int(a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1}; const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1}; const string abc="abcdefghijklmnopqrstuvwxyz"; const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const ld pi = 3.14159265; const int mod = 1e9 + 7; const int MOD = 1e9 + 7; const int MAXN = 1e6 + 7; const int inf = mod; const ll INF = 1e18; const ll zero = ll(0); const int logo = 20; const int off = 1 << logo; const int trsz = off << 1; //fa-fb zabranjeni brid int fa, fb, n, a, b; vi g[MAXN]; int par[MAXN][logo], dep[MAXN]; vii edges; int getLCA(int a, int b){ if(dep[a] < dep[b]) swap(a, b); int delta = dep[a] - dep[b]; for(int i=0; i<logo; i++) if(delta & (1 << i)) a = par[a][i]; if(a == b) return a; for(int i=logo-1; i>=0; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i]; return par[a][0]; } void dfs(int u, int p = 1){ par[u][0] = p; for(auto x: g[u]){ if(x == p) continue; dep[x] = dep[u] + 1; dfs(x, u); } } bool cmp(int a, int b){ return a > b; } int solve(int u, int p = -1){ vi tmp; for(auto x: g[u]){ if(x == p) continue; if(u == fa and x == fb) continue; if(u == fb and x == fa) continue; tmp.PB(solve(x, u)); } sort(all(tmp), cmp); int ret = 0; for(int i=0; i<tmp.size(); i++) ret = max(ret, tmp[i] + (i + 1)); return ret; } int calc(){ return max(solve(a), solve(b)); } void solve(){ cin >> n >> a >> b; for(int i=1, u, v; i < n; i++) cin >> u >> v, g[u].PB(v), g[v].PB(u); dfs(1); for(int i=1; i<=n; i++) for(int j=1; j<logo; j++) par[i][j] = par[par[i][j-1]][j-1]; int c = getLCA(a, b); //int ans = inf; //pretvori u bin search int sa = a; while(sa != c){ fa = sa; sa = par[sa][0]; fb = sa; //ans = min(ans, calc()); edges.PB(MP(fa, fb)); } vii tmp; //pretvroi u bin search int sb = b; while(sb != c){ fa = sb; sb = par[sb][0]; fb = sb; //ans = min(ans, calc()); tmp.PB(MP(fb, fa)); } reverse(all(tmp)); for(auto x: tmp) edges.PB(x); //for(auto x: edges) cout << x.X << " " << x.Y << "\n"; int lo = 0, hi = edges.size() - 1; int ans = inf; while(lo <= hi){ int mid = (lo + hi) / 2; int fa = edges[mid].X, fb = edges[mid].Y; int vala = solve(a); int valb = solve(b); ans = min(ans, max(vala, valb)); if(vala < valb) lo = mid + 1; else hi = mid - 1;; } lo = 0, hi = edges.size() - 1; while(lo <= hi){ int mid = (lo + hi) / 2; int fa = edges[mid].X, fb = edges[mid].Y; int vala = solve(a); int valb = solve(b); ans = min(ans, max(vala, valb)); if(vala < valb) hi = mid - 1; else lo = mid + 1; } cout << ans << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t=1; //cin >> t; while(t--)solve(); return 0; }

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

torrent.cpp: In function 'int solve(int, int)':
torrent.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i=0; i<tmp.size(); i++) ret = max(ret, tmp[i] + (i + 1));
      |               ~^~~~~~~~~~~
torrent.cpp: In function 'void solve()':
torrent.cpp:146:7: warning: unused variable 'fa' [-Wunused-variable]
  146 |   int fa = edges[mid].X, fb = edges[mid].Y;
      |       ^~
torrent.cpp:146:26: warning: unused variable 'fb' [-Wunused-variable]
  146 |   int fa = edges[mid].X, fb = edges[mid].Y;
      |                          ^~
torrent.cpp:157:7: warning: unused variable 'fa' [-Wunused-variable]
  157 |   int fa = edges[mid].X, fb = edges[mid].Y;
      |       ^~
torrent.cpp:157:26: warning: unused variable 'fb' [-Wunused-variable]
  157 |   int fa = edges[mid].X, fb = edges[mid].Y;
      |                          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...