제출 #680952

#제출 시각아이디문제언어결과실행 시간메모리
680952nicky4321경주 (Race) (IOI11_race)C++14
0 / 100
12 ms24916 KiB
#include <iostream> #include <cstring> #include <string> #include <map> #include <cmath> #include <vector> #include <set> #include <algorithm> #include <queue> #include <bitset> #include <deque> #include <stack> #include <array> #include <cassert> #define ll long long #define ld long double #define F first #define S second #define PB push_back #define MK make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<double, double> #define ALL(x) x.begin(), x.end() #define vi vector<int> #define vl vector<ll> #define SZ(x) (int)x.size() #define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++) #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int MAX = 1 << 20, MOD = 1e9 + 7; vector<pii> edge[MAX]; int cnt[MAX], vis[MAX], w[MAX]; int n, k, half; int ans = 2e9; map<ll, int> dis; void dfs(int now, int from){ cnt[now] = 1; for(pii y : edge[now]){ int i = y.F; if(i == from || vis[i]) continue; dfs(i, now); cnt[now] += cnt[i]; } } int find(int now, int from){ for(pii y : edge[now]){ int i = y.F; if(i == from || vis[i]) continue; if(cnt[i] > half) return find(i, now); } return now; } void calc1(int now, int from, int d, ll val, int cnt){ if(val > k) return; if(dis.count(k - val)){ ans = min(ans, cnt + dis[k - val]); } for(pii y: edge[now]){ int i = y.F; if(vis[i] || i == from) continue; calc1(i, now, d + 1, val + y.S, cnt + 1); } } void calc2(int now, int from, int d, ll val, int cnt){ if(val > k) return; if(dis.count(val)) dis[val] = min(dis[val], cnt); else dis[val] = cnt; for(pii y : edge[now]){ int i = y.F; if(vis[i] || i == from) continue; calc2(i, now, d + 1, val + y.S, cnt + 1); } } void solve(int x){ dfs(x, x); half = cnt[x] / 2; int c = find(x, x); // cout << c << '\n'; vis[c] = 1; dis[0] = 1; for(pii i : edge[c]){ int y = i.F; if(!vis[y]){ calc1(y, y, 1, 0, 1); calc2(y, y, 1, 0, 1); } } dis.clear(); for(pii i : edge[c]){ if(!vis[i.F]) solve(i.F); } } int best_path(int N, int K, int H[][2], int L[]){ IOS n = N; k = K; for(int i = 0;i < n - 1;i++){ edge[H[i][0]].PB(MK(H[i][1], i)); edge[H[i][1]].PB(MK(H[i][0], i)); w[i] = L[i]; } solve(0); return ans; }

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

race.cpp: In function 'void calc2(int, int, int, long long int, int)':
race.cpp:75:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   75 |     if(val > k)
      |     ^~
race.cpp:77:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   77 |  if(dis.count(val))
      |  ^~
race.cpp:79:5: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   79 |     else
      |     ^~~~
race.cpp:81:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   81 |  for(pii y : edge[now]){
      |  ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...