Submission #1074227

#TimeUsernameProblemLanguageResultExecution timeMemory
1074227TrumlingDreaming (IOI13_dreaming)C++14
0 / 100
51 ms14932 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define F first #define S second #define enter cout<<'\n'; #define INF 99999999999999999 #define MOD 1000000007 #define all(x) x.begin(),x.end() vector<vector<pair<ll,ll>>>g; vector<bool>vis; ll n,m; void dfs1(int start,ll &count) { for(auto x:g[start]) if(!vis[x.F]) { vis[x.F]=1; count+=x.S; dfs1(x.F, count); } } void dfs2(int start,int pre,ll &ans,ll diff,ll curr,ll count) { if(diff > abs((count-curr)-curr)) { ans=max(curr,count-curr); diff= abs((count-curr)-curr); } for(auto x:g[start]) if(x.F!=pre) dfs2(x.F,start,ans,diff,curr + x.S,count); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N; m=M; g.assign(n,vector<pair<ll,ll>>()); vis.assign(n,0); for(int i=0;i<m;i++) { g[A[i]].pb({B[i],T[i]}); g[B[i]].pb({A[i],T[i]}); } vector<ll>ans(2,0); ll ansi=0; ll idx=0; for(int i=0;i<N;i++) if(!vis[i] && g[i].size()==1) { vis[i]=1; ll count=0; dfs1(i,count); ansi=max(ansi,count); dfs2(i,i,ans[idx++],count,0,count); } return max(ansi,ans[0] + ans[1] + L); }
#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...