Submission #196870

#TimeUsernameProblemLanguageResultExecution timeMemory
196870awlintqaaDreaming (IOI13_dreaming)C++14
0 / 100
1006 ms13804 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 340 #define mid (l+r)/2 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase #define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset typedef long long ll; typedef long double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; const ll mod=1000000007;//998244353; const ll inf=1e18*4; const ld pai=acos(-1); #include "dreaming.h" ll n,m,mx,id,timer=1; vpll v[100009]; ll done[100009]; ll MN[100009],who[100009]; void fill(ll node){ done[node]=timer; for(auto u:v[node]){ if(done[u.fi])C; fill(u.fi); } } void MX(ll node,ll p,ll crnt){ if(crnt>mx)mx=crnt,id=node; for(auto u:v[node]){ if(u.fi==p)C; MX(u.fi,node,crnt+u.se); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N,m=M; for(int i=0;i<m;i++){ int a=A[i],b=B[i],c=T[i]; v[a].pb({b,c}); v[b].pb({a,c}); } for(int i=0;i<n;i++){ MN[i]=1e9; if(done[i])C; fill(i); timer++; } for(int i=0;i<n;i++){ mx=0; MX(i,i,0); if(MN[done[i]]>mx){ MN[done[i]]=mx; who[done[i]]=i; } } vpi all; for(int i=1;i<timer;i++){ all.pb({MN[i],who[i]}); } sort(all.begin(),all.end()); reverse(all.begin(),all.end()); for(int i=1;i<(int)all.size();i++){ ll a=all[0].se,b=all[i].se,c=L; v[a].pb({b,c}); v[b].pb({a,c}); } mx=id=-1; MX(0,0,0); mx=-1; MX(id,id,0); return mx; }
#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...