Submission #875684

#TimeUsernameProblemLanguageResultExecution timeMemory
875684Elvin_FritlDreaming (IOI13_dreaming)C++17
100 / 100
61 ms15716 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 545 , inf = 1e9 + 199; #include "dreaming.h" vector<pair<int , int>> g[N]; vector<int> color(N) , dp(N , 1) , dp2(N , 0) , dp3(N , 0),pre(N,0),pre1(N,0); int mx = -1 , ind = -1; void dfs(int s , int p) { color[s] = 1; if(dp[s] > mx){ mx=dp[s]; ind=s; } for(auto &i : g[s]) { if( i.first == p){ continue; } dp[ i.first ] = dp[s] + i.second; pre[i.first]=s; pre1[i.first]=i.second; dfs( i.first , s); } } int travelTime(int n, int m, int l, int A[], int B[], int T[]) { for(int i=0;i<m;i++) { g[A[i]].push_back({B[i] , T[i]}); g[B[i]].push_back({A[i] , T[i]}); } vector<int> atvet; int cavab=0; for(int i=0;i<n;i++) { if(color[i] == 0) { mx=ind=-1; dp[i]=0; dfs(i , i); int ind1=ind; mx=ind=-1; dp[ind1]=0; dfs(ind1 , ind1); int e=ind; int mx1=mx; int sum=0; while(e!=ind1){ sum+=pre1[e]; e=pre[e]; mx1=min(mx1,max(mx-sum,sum)); } atvet.push_back(mx1); cavab=max(cavab,mx); } } sort(atvet.begin() , atvet.end()); reverse(atvet.begin() , atvet.end()); if(atvet.size()>=2){ cavab=max(cavab,atvet[0]+atvet[1]+l); } if(atvet.size()>=3){ cavab=max(cavab,atvet[1]+atvet[2]+2*l); } return cavab; }
#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...