Submission #1012431

#TimeUsernameProblemLanguageResultExecution timeMemory
1012431amirhoseinfar1385Dreaming (IOI13_dreaming)C++17
0 / 100
1008 ms16460 KiB
#include "dreaming.h" #include<bits/stdc++.h> using namespace std; const int maxn=100000+10; struct yal{ int u,v,w; int getad(int fu){ return (u^v^fu); } }alle[maxn]; int n,m,l,mainres=0,vis[maxn]; vector<int>adj[maxn]; pair<int,int>mx[maxn]; pair<int,int>comp(pair<int,int>a,int b){ if(b>a.first){ a.first=b; if(a.first>a.second){ swap(a.first,a.second); } } return a; } void dfsdown(int u,int par=-1){ mx[u]=make_pair(0,0); for(auto x:adj[u]){ int v=alle[x].getad(u); if(v==par){ continue; } dfsdown(v,u); mx[u]=comp(mx[u],mx[v].second+alle[x].w); } return ; } void dfsup(int u,int par=-1,int l=-1){ mx[u]=comp(mx[u],l); mainres=max(mainres,mx[u].first+mx[u].second); for(auto x:adj[u]){ int v=alle[x].getad(u); if(v==par){ continue; } int z=mx[u].second; if(mx[u].second==mx[v].second+alle[x].w){ z=mx[u].first; } dfsup(v,u,z); } } int get(int u,int par=-1){ int ret=u; for(auto x:adj[u]){ int v=alle[x].getad(u); if(v==par){ continue; } int r=get(v,u); if(mx[ret].second>mx[r].second){ ret=r; } } return ret; } int calc(int u){ dfsdown(u); dfsup(u); return get(u); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N; m=M; l=L; for(int i=0;i<m;i++){ alle[i].u=A[i]; alle[i].v=B[i]; alle[i].w=T[i]; adj[alle[i].u].push_back(i); adj[alle[i].v].push_back(i); } vector<int>alls; for(int i=1;i<=n;i++){ if(vis[i]==0){ alls.push_back(calc(i)); } } sort(alls.rbegin(),alls.rend()); if((int)alls.size()==2){ mainres=max(mainres,alls[0]+alls[1]+l); } if((int)alls.size()>=3){ mainres=max(mainres,alls[0]+alls[1]+l); mainres=max(mainres,alls[1]+alls[2]+2*l); } return mainres; }
#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...