제출 #463804

#제출 시각아이디문제언어결과실행 시간메모리
463804ezdp경주 (Race) (IOI11_race)C++14
0 / 100
4 ms2124 KiB
#pragma GCC target ("sse4") #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define endl '\n' #define pb push_back #define fr first #define sc second #define ll long long int #define ld long double #define bit(idx) idx&(-idx) #define bin(x) bitset<32>(x).to_string() #define all(A) A.begin(), A.end() #define de(x) cout << #x << " = " << x << endl; using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T> using matrix = vector<vector<T>>; /// find_by_order(x) -> x-th element in the set /// order_of_key(x) -> how many elements are smaller than x /// insert(x) -> inserts x into the set const ll MAXN = 2e5 + 5; const ll MAXL = 18; const ll INF = 1e16 + 16; ll n, k, up[MAXN][MAXL], len[MAXN], depth[MAXN], tin[MAXN], tout[MAXN], T, ans = INF, root = 1, used[MAXN], sz[MAXN], mn[MAXN]; matrix<pair<ll, ll>> G; matrix<ll> C; vector<pair<ll, ll>> upd; set<ll> rem; void dfs_lca(ll u = 1, ll p = 1, ll d = 0, ll L = 0){ tin[u] = ++ T; depth[u] = d; len[u] = L; up[u][0] = p; for(int i = 1; i < MAXL; i ++) up[u][i] = up[up[u][i - 1]][i - 1]; for(auto [v, l] : G[u]){ if(v != p){ dfs_lca(v, u, d + 1, L + l); } } tout[u] = ++ T; } bool is_ancestor(ll u, ll v){ return (tin[u] <= tin[v] && tout[v] <= tout[u]); } ll lca(ll u, ll v){ if(is_ancestor(u, v)) return u; if(is_ancestor(v, u)) return v; for(int i = MAXL - 1; i >= 0; i --){ if(!is_ancestor(up[u][i], v)){ u = up[u][i]; } } return up[u][0]; } pair<ll, ll> dist(ll u, ll v){ ll lc = lca(u, v); return {depth[u] + depth[v] - 2 * depth[lc], len[u] + len[v] - 2 * len[lc]}; } ll find_size(ll u, ll p = -1){ if(used[u]) return 0; sz[u] = 1; for(auto [v, l] : G[u]){ if(v != p && !used[v]){ sz[u] += find_size(v, u); } } return sz[u]; } ll find_centroid(ll u, ll p, ll cn){ for(auto [v, l] : G[u]){ if(v != p && !used[v] && sz[v] > cn / 2){ return find_centroid(v, u, cn); } } return u; } void init_centroid(ll u = 1, ll p = -1){ find_size(u); ll c = find_centroid(u, -1, sz[u]); used[c] = true; if(p == -1){ root = c; } else{ C[c].pb(p); C[p].pb(c); } for(auto [v, l] : G[c]){ if(!used[v]){ init_centroid(v, c); } } } void dfs2(ll u, ll p, ll c){ auto tmp = dist(u, c); if(tmp.sc <= k){ ans = min(ans, mn[k - tmp.sc] + tmp.fr); upd.pb({tmp.sc, tmp.fr}); rem.insert(tmp.sc); } for(auto v : C[u]){ if(v != p){ dfs2(v, u, c); } } } void dfs1(ll u, ll p){ mn[0] = 0; for(auto v : C[u]){ dfs2(v, u, u); for(auto [x, v] : upd) mn[x] = min(mn[x], v); } for(auto x : rem) mn[x] = INF; for(auto v : C[u]){ if(v != p){ dfs1(v, u); } } } int best_path(int N, int K, int h[][2], int L[]){ n = N; k = K; C = matrix<ll>(n + 1); G = matrix<pair<ll, ll>>(n + 1); for(int i = 0; i < n - 1; i ++){ G[h[i][0]].pb({h[i][1], L[i]}); G[h[i][1]].pb({h[i][0], L[i]}); } for(int i = 0; i < MAXN; i ++) mn[i] = INF; dfs_lca(); init_centroid(); dfs1(root, root); return (ans == INF ? -1 : ans); }

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

race.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
race.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
race.cpp: In function 'void dfs_lca(long long int, long long int, long long int, long long int)':
race.cpp:46:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'long long int find_size(long long int, long long int)':
race.cpp:80:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'long long int find_centroid(long long int, long long int, long long int)':
race.cpp:89:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |  for(auto [v, l] : G[u]){
      |           ^
race.cpp: In function 'void init_centroid(long long int, long long int)':
race.cpp:103:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |  for(auto [v, l] : G[c]){
      |           ^
race.cpp: In function 'void dfs1(long long int, long long int)':
race.cpp:128:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |   for(auto [x, v] : upd) mn[x] = min(mn[x], v);
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...