제출 #1174125

#제출 시각아이디문제언어결과실행 시간메모리
1174125StefanSebezDreaming (IOI13_dreaming)C++20
65 / 100
232 ms25064 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double const int N=1e5+50; int n,m,L; vector<pair<int,int>>E[N]; map<pair<int,int>,int>edge; int maksdepth,makscvor,par[N]; int komp[N],cnt; void DFS(int u,int parent,int depth){ par[u]=parent; if(maksdepth<=depth) makscvor=u; maksdepth=max(maksdepth,depth); komp[u]=cnt; for(auto [i,x]:E[u]){ if(i==parent) continue; DFS(i,u,depth+x); } } int travelTime(int n1, int m1, int L1, int A[], int B[], int T[]) { n=n1,m=m1,L=L1; for(int i=0;i<m;i++){ E[A[i]].pb({B[i],T[i]}); E[B[i]].pb({A[i],T[i]}); edge[{A[i],B[i]}]=edge[{B[i],A[i]}]=T[i]; } vector<pair<int,int>>a; for(int i=0;i<n;i++){ //printf("%i\n",i); if(komp[i]) continue; cnt++; maksdepth=makscvor=-1; DFS(i,-1,0); int u=makscvor; maksdepth=makscvor=-1; DFS(u,-1,0); int v=makscvor,d=maksdepth,d1=0; int val=1e9; while(v!=-1){ val=min(val,max(d,d1)); int x=edge[{v,par[v]}]; d-=x,d1+=x; v=par[v]; } a.pb({maksdepth,val}); } //for(int i=0;i<n;i++) printf("%i: %i\n",i,komp[i]); //for(auto [u,v]:a) printf("%i %i\n",u,v); sort(a.begin(),a.end()); for(int i=0;i+1<a.size();i++){ pair<int,int>x=a[i],y=a.back(); if(x.se+y.se+L>y.fi){ a.back().fi=x.se+y.se+L; a.back().se=min(max(x.se+L,y.se),max(x.se,y.se+L)); } } return a.back().fi; }
#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...