제출 #228145

#제출 시각아이디문제언어결과실행 시간메모리
228145caoash경주 (Race) (IOI11_race)C++14
100 / 100
551 ms74872 KiB
#pragma GCC target ("sse4") #include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include "race.h" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef pair<int, pi> pii; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; #define fax(i, a) for (int i = 0; i < (a); i++) #define f0x(i, a, b) for (int i = (a); i < (b); i++) #define f0xd(i,a,b) for (int i = (b)-1; i >= (a); i--) #define faxd(i,a) for (int i = (a)-1; i >= 0; i--) #define trav(a, x) for (auto& a : x) #define memeset memset #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define rsz resize template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template <class T, int ...Ns> struct BIT { T val = 0; void upd(T v) { val += v; } T query() { return val; } }; template <class T, int N, int... Ns> struct BIT<T, N, Ns...> { BIT<T,Ns...> bit[N + 1]; template<typename... Args> void upd(int pos, Args... args) { for (; pos <= N; pos += (pos&-pos)) bit[pos].upd(args...); } template<typename... Args> T sum(int r, Args... args) { T res = 0; for (; r; r -= (r&-r)) res += bit[r].query(args...); return res; } template<typename... Args> T query(int l, int r, Args... args) { return sum(r,args...)-sum(l-1,args...); } }; namespace input { template<class T> void re(complex<T>& x); template<class T1, class T2> void re(pair<T1,T2>& p); template<class T> void re(vector<T>& a); template<class T, size_t SZ> void re(array<T,SZ>& a); template<class T> void re(T& x) { cin >> x; } void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template<class T, class... Ts> void re(T& t, Ts&... ts) { re(t); re(ts...); } template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); } template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); } template<class T> void re(vector<T>& a) { fax(i,sz(a)) re(a[i]); } template<class T, size_t SZ> void re(array<T,SZ>& a) { fax(i,SZ) re(a[i]); } } using namespace input; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(ld x) { cout << x; } void pr(char x) { cout << x; } void pr(const char* x) { cout << x; } void pr(const string& x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template<class T1, class T2> void pr(const pair<T1,T2>& x); template<class T> void pr(const T& x); template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { pr(t); pr(ts...); } template<class T1, class T2> void pr(const pair<T1,T2>& x) { pr("{",x.f,", ",x.s,"}"); } template<class T> void pr(const T& x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { pr("]\n"); } // debug w/ commas template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[",#x,"] = ["), pc(x); } using namespace output; namespace io { void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO } } using namespace io; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); const int MOD = 1000000007; // 998244353 const ll INF = 1e18; const int MX = 200005; const ld PI = 4*atan((ld)1); vector<pair<int,ll>> adj[MX]; map<ll,ll> sack[MX]; ll K; ll ans = INT_MAX; void dfs(int v, int p, ll d, ll dist){ for(pi to : adj[v]){ if(to.f != p){ dfs(to.f, v, d+1, dist + to.s); if(sz(sack[v]) < sz(sack[to.f])){ swap(sack[v], sack[to.f]); } //dbg(to.f, sack[to.f]); trav(x, sack[to.f]){ if(sack[v].count(dist+(K-(x.f-dist)))){ ckmin(ans, abs(sack[v][dist+(K-(x.f-dist))] + sack[to.f][x.f])-(2*d)); } if((x.f-dist) == K){ ckmin(ans, x.s-d); } } trav(x, sack[to.f]){ if(sack[v].count(x.f)){ ckmin(sack[v][x.f], sack[to.f][x.f]); } else{ sack[v][x.f] = sack[to.f][x.f]; } } sack[to.f].clear(); } } sack[v][dist] = d; if(sack[v].count(dist+K)){ ckmin(ans, sack[v][dist+K]-d); } } int best_path(int N, int nK, int H[][2], int L[]){ K = (ll)nK; fax(i,N-1){ int u = H[i][0]; int v = H[i][1]; ll w = (ll)L[i]; adj[u].pb({v,w}); adj[v].pb({u,w}); } dfs(0,-1, 0, 0); trav(curr, sack[0]){ if(curr.f == K){ ckmin(ans, curr.s); } } return (ans == INT_MAX ? -1 : ans); } /* int main() { setIO(); int N,K; re(N,K); int H[N][2]; int L[N]; fax(i,N-1){ re(H[i][0], H[i][1], L[i]); } pr(best_path(N,K,H,L), "\n"); } */

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

race.cpp: In function 'void io::setIn(std::__cxx11::string)':
race.cpp:134:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void io::setOut(std::__cxx11::string)':
race.cpp:135:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...