이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)
void setIO(string s) {
if (sz(s) != 0) {
freopen((s+".inp").c_str(),"r",stdin);
//freopen((s+".out").c_str(),"w",stdout);
}
}
void setIOusaco(string s) {
if (sz(s) != 0) {
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}
void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
const int MAXN = 200007;
const int MAXK = 1000007;
int n, k, ans, min_depth[MAXK], s[MAXN], r[MAXN];
vt<pair<int, int> > ke[MAXN], paths;
int dfs(int u, int p = -1) {
s[u] = 1;
trav(c, ke[u]) {
int v = c.ff;
if (v == p || r[v]) continue;
s[u] += dfs(v, u);
}
return s[u];
}
int find_centroid(int u, int ms, int p = -1) {
trav(c, ke[u]) {
int v = c.ff;
if (v == p || r[v] || s[v]*2 < ms) continue;
return find_centroid(v, ms, u);
}
return u;
}
void dfs2(int u, int p = -1, int depth = 0, int len = 0) {
if (p != -1) paths.pb(mp(len, depth));
trav(c, ke[u]) {
int v = c.ff;
int val = c.ss;
if (v == p || r[v]) continue;
dfs2(v, u, depth+1, len+val);
}
}
void centroid(int u) {
int tree_centroid = find_centroid(u, dfs(u));
r[tree_centroid] = 1;
dfs2(tree_centroid);
fto(i, 0, sz(paths)-1) {
if (paths[i].ss == 1) {
fto(j, i, sz(paths)-1) {
if (k-paths[j].ff >= 0 && k-paths[j].ff <= 1000000) ans = min(ans, min_depth[k-paths[j].ff] + paths[j].ss);
if (j == sz(paths) || paths[j+1].ss == 1) break;
}
}
if (paths[i].ff > 0 && paths[i].ff <= 1000000) ckmin(min_depth[paths[i].ff], paths[i].ss);
}
trav(c, paths) if(c.ff > 0 && c.ss <= 1000000) min_depth[c.ff] = (int)1e9;
paths.clear();
trav(c, ke[tree_centroid]) {
int v = c.ff;
if (!r[v]) centroid(v);
}
}
int best_path(int n_, int k_, int edges[][2], int weights[]){
//setIO("race_ioi2011");
//ios::sync_with_stdio(false); cin.tie(0);
n = n_;
k = k_;
fto(i, 0, n-2) {
int u = edges[i][0];
int v = edges[i][1];
int l = weights[i];
ke[u].pb(mp(v, l));
ke[v].pb(mp(u, l));
}
ans = (int)1e9;
min_depth[0] = 0;
fto(i, 1, 1000000) min_depth[i] = (int)1e9;
centroid(0);
return ((ans == (int)1e9) ? -1 : ans);
}
//int main() {
// setIO("race_ioi2011");
// ios::sync_with_stdio(false); cin.tie(0);
//
//
// cin >> n >> k;
// fto(i, 0, n-2) {
// int u, v, l;
// cin >> u >> v >> l;
// ke[u].pb(mp(v, l));
// ke[v].pb(mp(u, l));
// }
//
// ans = (int)1e9;
// min_depth[0] = 0;
// fto(i, 1, 1000000) min_depth[i] = (int)1e9;
//
// centroid(0);
//
// cout << ((ans == (int)1e9) ? -1 : ans) << '\n';
//
// return 0;
//}
컴파일 시 표준 에러 (stderr) 메시지
race.cpp: In function 'void setIO(std::string)':
race.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
26 | freopen((s+".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void setIOusaco(std::string)':
race.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |