제출 #426787

#제출 시각아이디문제언어결과실행 시간메모리
426787LittlePants경주 (Race) (IOI11_race)C++17
21 / 100
3073 ms28896 KiB
#include "race.h" #include<bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") #pragma loop-opt(on) #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,tune=native") #define pb push_back #define eb emplace_back #define push emplace #define lb(x, v) lower_bound(all(x), v) #define ub(x, v) upper_bound(all(x), v) #define sz(x) (int)(x.size()) #define re(x) reverse(all(x)) #define uni(x) x.resize(unique(all(x)) - x.begin()) #define all(x) x.begin(), x.end() #define mem(x, v) memset(x, v, sizeof x); #define pii pair<int, int> #define inf 1e9 #define INF 1e18 #define mod 1000000007 #define F first #define S second #define IO ios_base::sync_with_stdio(0); cin.tie(0); #define chmax(a, b) (a = (b > a ? b : a)) #define chmin(a, b) (a = (b < a ? b : a)) using namespace std; void trace_() {cerr << "\n";} template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); } #define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__); const int mxN = 2e5 + 5; int n, k, ans = inf, sz[mxN], bson[mxN], bw[mxN]; vector<pii> g[mxN]; void pre(int u, int p) { sz[u] = 1; int id = -1, ww = 0; for (auto [v, w] : g[u]) { if (v == p) continue; pre(v, u); sz[u] += sz[v]; if (id == -1 or sz[id] < sz[v]) id = v, ww = w; } bson[u] = id; bw[u] = ww; } map<int, int> dfs(int u, int p) { map<int, int> mp, t; if (~bson[u]) { t = dfs(bson[u], u); for (auto [len, step] : t) mp[len + bw[u]] = step + 1; } mp[0] = 0; for (auto [v, w] : g[u]) { if (v == bson[u] or v == p) continue; t = dfs(v, u); for (auto [len, step] : t) { if (len + w <= k and mp.count(k - len - w)) { chmin(ans, mp[k - len - w] + step + 1); } if (mp.count(len + w)) { chmin(mp[len + w], step + 1); } else { mp[len + w] = step + 1; } } } if (mp.count(k)) { ans = min(ans, mp[k]); } return mp; } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; 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]}); bson[i] = -1; } bson[n - 1] = -1; pre(0, -1); dfs(0, -1); if (ans > n) ans = -1; return ans; }

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

race.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...