Submission #838910

#TimeUsernameProblemLanguageResultExecution timeMemory
838910nninDreaming (IOI13_dreaming)C++14
0 / 100
36 ms15688 KiB
#include "dreaming.h" #include<bits/stdc++.h> #define f first #define s second using namespace std; vector<pair<int, int>> adj[100005]; vector<int> group[100005]; int maxdis[100005], n; bool vis[100005]; int dsu[100005]; int par(int x) { if(dsu[x]==x) return x; return dsu[x] = par(dsu[x]); } void dfs(int cur, int prev, int dis) { maxdis[cur] = max(maxdis[cur], dis); for(auto next:adj[cur]) { if(prev==next.f) continue; dfs(next.f, cur, dis+next.s); } } int mnGroup(int i) { int last = n; for(int j=1;j<group[i].size();j++) { int st = n; for(int node:group[i]) { if(!vis[node] && maxdis[node]>=maxdis[st] && maxdis[node]>=maxdis[last]) st = node; } if(st==n) break; dfs(st, -1, 0); vis[st] = 1; last = st; } int ret = INT_MAX; for(int mxdis:group[i]) { ret = min(ret, maxdis[mxdis]); } return ret; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N; for(int i=0;i<N;i++) dsu[i] = i; for(int i=0;i<M;i++) { adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); dsu[par(A[i])] = par(B[i]); } for(int i=0;i<N;i++) group[par(i)].push_back(i); int mx = -1, mx2 = -1; for(int i=0;i<N;i++) { if(group[i].empty()) continue; int mn = mnGroup(i); if(mn >= mx) { mx2 = mx; mx = mn; } else if(mn > mx2) { mx2 = mn; } } if(mx2==-1) return mx; return mx+mx2+L; }

Compilation message (stderr)

dreaming.cpp: In function 'int mnGroup(int)':
dreaming.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int j=1;j<group[i].size();j++) {
      |                 ~^~~~~~~~~~~~~~~~
#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...