제출 #600985

#제출 시각아이디문제언어결과실행 시간메모리
600985Meloric경주 (Race) (IOI11_race)C++14
0 / 100
1 ms340 KiB
#pragma GCC optimize("O3") #include "race.h" #include <bits/stdc++.h> #define pb push_back #define int int64_t #define pii pair<int, int> #define X first #define Y second #define all(x) (x).begin(),(x).end() #define lb lower_bound #define ub upper_bound #define speSet pair<pii, set<pii>> using namespace std; const int inf = 1e8; 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; } int find(int 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; } int size(){ return S.size(); } void p(){ //for(auto [e, f] : S)cout << e+delta.X << ' '<< f+delta.Y << endl; } */ }; signed best_path(signed N, signed K, signed H[][2], signed L[]) { int n = N; int k = K; vector<vector<pii>> g(n, vector<pii>()); for(int i = 0; i< n-1; i++){ int c = H[i][0]; int d = H[i][1]; int w = L[i]; g[c].pb({d, w}); g[d].pb({c, w}); } int ret = inf; vector<speSet>A(n); auto dfs = [&](auto&&self, int u, int p)->void{ A[u].Y.insert({0, 0}); for(auto [v, w] : g[u])if(v!=p){ self(self, v, u); A[v].X.X+=w; A[v].X.Y+=1; if(A[u].Y.size() < A[v].Y.size())swap(A[u], A[v]); auto [vx, vy] = A[v].X; auto [ux, uy] = A[u].X; for(auto [ex, ey] : A[v].Y){ ex+=vx; ey+=vy; auto it = A[u].Y.lb({k-ex-ux, -1}); if(it != A[u].Y.end() && it->X+ux == k-ex)ret=min(ret, ey+it->Y+uy); } for(auto [ex, ey] : A[v].Y){ ex = ex+vx-ux; ey = ey+vy-uy; A[u].Y.insert({ex, ey}); } } }; /* auto dfs = [&](auto&& self, int u, int p)->special_set*{ //cout << u << endl; special_set* S = new 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; }; */ dfs(dfs, 0, 0); if(ret == inf)return -1; return ret; } /* void solve(){ signed 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:20:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void p(auto A){
      |        ^~~~
race.cpp: In lambda function:
race.cpp:74:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |    for(auto [v, w] : g[u])if(v!=p){
      |             ^
race.cpp:79:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     auto [vx, vy] = A[v].X;
      |          ^
race.cpp:80:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     auto [ux, uy] = A[u].X;
      |          ^
race.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for(auto [ex, ey] : A[v].Y){
      |              ^
race.cpp:86:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     for(auto [ex, ey] : A[v].Y){
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...