제출 #600507

#제출 시각아이디문제언어결과실행 시간메모리
600507Meloric경주 (Race) (IOI11_race)C++14
43 / 100
3084 ms91468 KiB
#pragma GCC optimize("O3") #include "race.h" #include <bits/stdc++.h> #define pb push_back #define ll int64_t #define pii pair<int64_t, int64_t> #define X first #define Y second #define all(x) (x).begin(),(x).end() #define lb lower_bound #define ub upper_bound using namespace std; const ll inf = 1e18; void p(auto A){ for(auto e : A)cout << e << ' '; cout << '\n'; } struct special_set{ set<pii> S; pii delta = {0, 0}; void insert(pii e){ S.insert({e.X-delta.X, e.Y-delta.Y}); } void update(pii dx){ delta.X+=dx.X; delta.Y+=dx.Y; } ll find(ll x){ x-=delta.X; if(S.lb({x, -inf}) == S.end())return inf; if(S.lb({x, -inf})->X != x)return inf; return S.lb({x, -inf})->Y+delta.Y; } pii pop(){ pii ret = *S.begin(); S.erase(S.begin()); ret.X+=delta.X; ret.Y+=delta.Y; return ret; } ll size(){ return S.size(); } void p(){ //for(auto [e, f] : S)cout << e+delta.X << ' '<< f+delta.Y << endl; } }; int best_path(int N, int K, int H[][2], int L[]) { ll n = N; ll k = K; vector<vector<pii>> g(n, vector<pii>()); for(ll i = 0; i< n-1; i++){ ll c = H[i][0]; ll d = H[i][1]; ll w = L[i]; g[c].pb({d, w}); g[d].pb({c, w}); } ll ret = inf; auto dfs = [&](auto&& self, ll u, ll p)->special_set{ //cout << u << endl; special_set S = special_set(); S.insert({0, 0}); vector<pii> V; for(auto [v, w] : g[u])if(v!=p){ special_set O = self(self, v, u); O.update(make_pair(w, 1ll)); if(S.size() < O.size())swap(S, O); while(O.size()){ pii e = O.pop(); //cout << u << ' '<< e.X << ' '<< e.Y << ' ' << endl; ret = min(ret, e.Y+S.find(k-e.X)); if(e.X > k)continue; V.pb(e); //S.insert(e); } for(auto e : V)S.insert(e); } return S; }; auto S = dfs(dfs, 0, 0); if(ret == inf)return -1; return ret; } /* void solve(){ int N, K, H[100][2], L[100]; cin >> N >> K; for(int i = 0; i< N-1; i++){ cin >> H[i][0] >> H[i][1] >> L[i]; } cout << best_path(N, K, H, L); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; //cin >> t; while(t--)solve(); } */

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

race.cpp:18:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void p(auto A){
      |        ^~~~
race.cpp: In lambda function:
race.cpp:73:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |    for(auto [v, w] : g[u])if(v!=p){
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...