제출 #1023548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023548		vjudge1	경주 (Race) (IOI11_race)	C++17	100 / 100	311 ms	54152 KiB

race

#include <bits/stdc++.h>
// #include "race.h"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ii = pair<int,int>; using ll = long long; using ull = unsigned long long;
using vi = vector<ll>;
void valid(int in){cout<<((in)?"YES\n":"NO\n");return;}
const int N = 1e6 + 7;
vector<ii> graph[N];
bool vis[N];int ans = 1e9, sz[N], mn[N],k;
void find_sz(int nodo ,int  p = -1){sz[nodo]=1;
    for(auto [v, cost] : graph[nodo]){if(v==p || vis[v] )continue;
        find_sz(v,nodo);
        sz[nodo] += sz[v];
    }
}
int find_cent(int nodo, int raiz, int p = -1){
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        if(sz[v]>sz[raiz]/2)return find_cent(v, raiz, nodo);
    }return nodo;
}
void dfs_calc(int nodo, int sum = 0,int nivel = 0, int p = -1){if(sum>k)return;
    ans = min(ans, mn[k-sum]+ nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_calc(v, sum + cost, nivel+1, nodo);
    }
}
void dfs_add(int nodo, int sum = 0,  int nivel = 0, int p = -1){if(sum>k)return;
    mn[sum] = min(mn[sum],nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_add(v, sum+cost, nivel+1, nodo);
    }
}
void dfs_del(int nodo, int sum = 0, int nivel = 0, int p = -1){
    if(sum>k)return;mn[sum] =1e9;
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_del(v, sum+cost, nivel+1, nodo);
    }
}
void solve(int nodo){if(vis[nodo])return;
    find_sz(nodo);int cen = find_cent(nodo,nodo);mn[0]=0;
    for(auto [v,cost] : graph[cen]){if(vis[v])continue;
        dfs_calc(v, cost, 1,cen);
        dfs_add(v,cost, 1,cen);
    }dfs_del(cen);vis[cen]=1;
    for(auto [v,cost] : graph[cen])if(!vis[v])solve(v);
}
int best_path(int n, int K, int H[][2], int L[]){k=K;fill(mn, mn+k+3, 1e9);
    fo(i,n-1){
        graph[H[i][0]].pb({H[i][1], L[i]});
        graph[H[i][1]].pb({H[i][0], L[i]});
    }solve(0);return (ans == 1e9 ? -1 : ans);
}

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

race.cpp: In function 'void dfs_del(int, int, int, int)':
race.cpp:48:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |     if(sum>k)return;mn[sum] =1e9;
      |     ^~
race.cpp:48:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |     if(sum>k)return;mn[sum] =1e9;
      |                     ^~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57