Submission #858013

#TimeUsernameProblemLanguageResultExecution timeMemory
858013yusufhocaogluDreaming (IOI13_dreaming)C++17
0 / 100
1012 ms20608 KiB
#include "dreaming.h" #include <bits/stdc++.h> #define int long long #define pri pair<int,int> using namespace std; struct node { vector<pri> adj; }; int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) { vector<node> nodes(N); for (int i = 0;i<M;i++) { nodes[A[i]].adj.push_back({B[i],T[i]}); nodes[B[i]].adj.push_back({A[i],T[i]}); } auto bfs = [nodes,N](int src) { queue<int> q;q.push(src); vector<int> trail(N,1e9); vector<int> dist(N,-1); trail[src]=-1; dist[src]=0; while (q.size()) { auto f = q.front(); for (int i = 0;i<nodes[f].adj.size();i++) { if (nodes[f].adj[i].first==trail[f]) continue; trail[nodes[f].adj[i].first] = f; dist[nodes[f].adj[i].first] = dist[f] + nodes[f].adj[i].second; q.push(nodes[f].adj[i].first); } q.pop(); } return pair<vector<int>,vector<int>>{dist,trail}; }; vector<int> visit(N,0); vector<int> paths; for (int i = 0;i<N;i++) { if (visit[i]==1) continue; auto res = bfs(i); pri mxd = {-1,-1}; for (int j = 0;j<N;j++) { if (res.second[j]!=1e9) visit[j]=1; if (res.first[j] > mxd.first) { mxd = {res.first[j],j}; } } auto res2 = bfs(mxd.second); mxd = {-1,-1}; for (int j = 0;j<N;j++) { if (res2.first[j] > mxd.first) { mxd = {res2.first[j],j}; } } int tl = mxd.first; int t = res2.second[mxd.second]; int mn = (t==-1)?0:1e9; while (t!=-1) { mn=min(mn,max(res2.first[t],tl-res2.first[t])); t = res2.second[t]; } paths.push_back(mn); } sort(paths.begin(),paths.end()); if (paths.size()==1) return paths[0]; else if (paths.size()==2) return paths[1]+paths[0]+L; else return max(paths[paths.size()-1]+paths[paths.size()-2]+L,paths[paths.size()-2]+paths[paths.size()-3]+2*L); //return 12; }

Compilation message (stderr)

dreaming.cpp: In lambda function:
dreaming.cpp:24:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             for (int i = 0;i<nodes[f].adj.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...