Submission #196850

#TimeUsernameProblemLanguageResultExecution timeMemory
196850awlintqaaDreaming (IOI13_dreaming)C++14
18 / 100
335 ms28784 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ppb pop_back #define C continue #define fi first #define se second typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pll> vpll; typedef vector<pi> vpi; #include "dreaming.h" ll n,m,k; vpll v[100009]; map<pll,ll>mp; ll done[100009]; vll ret,all; ll mx,id,z; void dfs1(int node,int p,ll crnt){ done[node]=1; if(crnt>=mx){ mx=crnt; id=node; } for(auto u:v[node]){ if(u.fi==p)C; dfs1(u.fi,node,crnt+u.se); } } void dfs2(int node,int p){ done[node]=1; if(!z)ret.pb(node); if(node==id){ z=1; return ; } for(auto u:v[node]){ if(u.fi==p)C; dfs2(u.fi,node); if(z)return ; } if(!z)ret.ppb(); } int find(){ vll X; X.resize((int)ret.size()); ll crnt=0; for(int i=0;i<ret.size();i++){ if(i)crnt+=mp[{ret[i],ret[i-1]}]; X[i]=max(X[i],crnt); } crnt=0; ll timer=ret.size()-1; for(int i=0;i<ret.size();i++){ if(i)crnt+=mp[{ret[i],ret[i-1]}]; X[timer]=max(X[timer],crnt); timer--; } ll mn=1e9*2; for(int i=0;i<X.size();i++){ mn=min(mn,X[i]); } return mn; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N,m=M,k=L; 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}); mp[{a,b}]=mp[{b,a}]=c; } for(int i=0;i<n;i++){ if(done[i])C; mx=id=-1; z=0; ret.clear(); dfs1(i,i,0); int xxx=id; mx=id=-1; dfs1(xxx,xxx,0); dfs2(xxx,xxx); all.pb(find()); } sort(all.begin(),all.end()); reverse(all.begin(),all.end()); ll mx=0; if(all.size()==1)mx=all[0]; if(all.size()==2)mx=all[0]+all[1]+L; if(all.size()>2){ mx=all[0]+all[1]+L; mx=max(mx,all[1]+all[2]+L+L); } return mx; }

Compilation message (stderr)

dreaming.cpp: In function 'int find()':
dreaming.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ret.size();i++){
                     ~^~~~~~~~~~~
dreaming.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ret.size();i++){
                     ~^~~~~~~~~~~
dreaming.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<X.size();i++){
                     ~^~~~~~~~~
#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...