제출 #962425

#제출 시각아이디문제언어결과실행 시간메모리
962425raspy경주 (Race) (IOI11_race)C++14
0 / 100
3 ms10392 KiB
#include "race.h" #include <unordered_map> #include <vector> #include <iostream> using namespace std; typedef long long ll; vector<pair<ll, ll>> graf[200005]; unordered_map<ll, ll> mp; bool rmv[200005]; ll sz[200005]; ll rez = -1; ll k = 0; ll sbsz(ll u, ll p) { sz[u] = 1; for (auto [v, w] : graf[u]) { if (rmv[v] || v == p) continue; sz[u] += sbsz(v, u); } return sz[u]; } ll gct(ll u, ll vel, ll p) { for (auto [v, w] : graf[u]) { if (rmv[v] || v == p) continue; if (sz[v]*2 > vel) return gct(v, vel, u); } return u; } void dfs(ll u, ll tr, ll gl, ll p, bool polni) { if (tr > k) return; if (polni) { if (mp.find(tr) == mp.end()) mp[tr] = gl; else mp[tr] = min(mp[tr], gl); } else { if (mp.find(k-tr) != mp.end()) rez = min((rez == -1 ? gl+mp[k-tr] : rez), gl+mp[k-tr]); } for (auto [v, w] : graf[u]) { if (rmv[v] || v == p) continue; dfs(v, tr+w, gl+1, u, polni); } } void decom(ll u) { ll ct = gct(u, sbsz(u, -1), -1); mp.clear(); rmv[ct] = 1; mp[0] = 0; for (auto [v, w] : graf[ct]) { if (rmv[v]) continue; dfs(v, w, 1, u, false); dfs(v, w, 1, u, true); } for (auto [v, w] : graf[ct]) if (!rmv[v]) decom(v); return; } int best_path(int N, int K, int H[][2], int L[]) { ll n = N; k = K; for (ll i = 0; i < n-1; i++) { ll u = H[i][0], v = H[i][1]; ll w = L[i]; // cout << "--> " << u << " " << v << " " << w << "\n"; graf[u].push_back({v, w}); graf[v].push_back({u, w}); } mp.clear(); decom(0); return rez; }

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

race.cpp: In function 'll sbsz(ll, ll)':
race.cpp:19:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'll gct(ll, ll, ll)':
race.cpp:30:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void dfs(ll, ll, ll, ll, bool)':
race.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for (auto [v, w] : graf[u])
      |            ^
race.cpp: In function 'void decom(ll)':
race.cpp:70:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |  for (auto [v, w] : graf[ct])
      |            ^
race.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |  for (auto [v, w] : graf[ct])
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...