제출 #964565

#제출 시각아이디문제언어결과실행 시간메모리
964565ReLiceDreaming (IOI13_dreaming)C++17
47 / 100
229 ms22208 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define ll int #define str string #define ins insert #define ld long double #define pb push_back #define pf push_front #define pof pop_front() #define pob pop_back() #define lb lower_bound #define ub upper_bound #define endl "\n" #define fr first #define sc second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz size() #define vll vector<ll> #define bc back() #define arr array #define pll vector<pair<ll,ll>> using namespace std; template<class S,class T> bool chmin(S &a,const T &b) { return a>b?(a=b)==b:false; } template<class S,class T> bool chmax(S &a,const T &b) { return a<b?(a=b)==b:false; } const ll mod=1e9+7; const ld eps=1e-9; const ll N=1e5+7; ll d[N]; vector<set<pair<ll,ll>>> g(N); ll mx,x; void dfs(ll v,ll p){ if(chmax(mx,d[v]))x=v; for(auto i : g[v]){ if(i.fr==p) continue; d[i.fr]=d[v]+i.sc; dfs(i.fr,v); } } int travelTime(ll n, ll m, ll l, ll a[], ll b[], ll t[]) { ll i,j; set<pair<ll,ll>> st; for(i=0;i<m;i++){ a[i]++; b[i]++; g[a[i]].ins({b[i],t[i]}); g[b[i]].ins({a[i],t[i]}); } ll ans=0; for(i=1;i<=n;i++){ if(!d[i]){ mx=0; dfs(i,0); mx=0; d[x]=0; dfs(x,0); chmax(ans,mx); } } vll v; for(i=1;i<=n;i++){ d[i]=0; if(g[i].sz==0){ v.pb(i); }else if(g[i].sz==1){ st.ins({g[i].begin()->sc,i}); } } while(st.sz){ ll x=st.begin()->sc; st.erase(st.begin()); for(auto i : g[x]){ g[i.fr].erase(g[i.fr].find({x,i.sc})); chmax(d[i.fr],d[x]+i.sc); if(g[i.fr].sz==0)v.pb(i.fr); else if(g[i.fr].sz==1)st.ins({d[i.fr]+g[i.fr].begin()->sc,i.fr}); } g[x].clear(); } for(i=0;i<v.sz;i++) v[i]=d[v[i]]; sort(all(v)); if(v.sz>1)chmax(ans,v.bc+v[v.sz-2]+l); return ans; }/* signed main(){ ll n,m,l; cin>>n>>m>>l; ll a[m],b[m],t[m]; for(ll i=0;i<m;i++) cin>>a[i]; for(ll i=0;i<m;i++) cin>>b[i]; for(ll i=0;i<m;i++) cin>>t[i]; cout<<travelTime(n,m,l,a,b,t)<<endl; }*/ /* 12 8 2 0 8 2 5 5 1 1 10 8 2 7 11 1 3 9 6 4 2 4 3 7 1 5 3 */

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

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(i=0;i<v.sz;i++) v[i]=d[v[i]];
      |              ^
dreaming.cpp:47:10: warning: unused variable 'j' [-Wunused-variable]
   47 |     ll i,j;
      |          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...