Submission #838920

#TimeUsernameProblemLanguageResultExecution timeMemory
838920nninDreaming (IOI13_dreaming)C++14
0 / 100
36 ms15304 KiB
#include "dreaming.h" #include<bits/stdc++.h> #define pii pair<int, int> #define f first #define s second using namespace std; vector<pii> adj[100005]; vector<int> group[100005]; int maxdis[100005]; bool vis[100005], vis0[100005]; void dfs(int cur, int prev, int dis) { maxdis[cur] = max(maxdis[cur], dis); for(pii next:adj[cur]) { if(prev==next.f) continue; dfs(next.f, cur, dis+next.s); } } void inGroup(int root, int cur, int prev) { group[root].push_back(cur); vis0[cur] = 1; for(pii next:adj[cur]) { if(next.f==prev) continue; inGroup(root, next.f, cur); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { 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]}); } for(int i=0;i<N;i++) { if(vis0[i]) continue; inGroup(i, i, -1); } int mx = -1, mx2 = -1, mx3 = -1, mxx = -1; for(int i=0;i<N;i++) { if(group[i].empty()) continue; 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 mn = INT_MAX; for(int mxdis:group[i]) { mn = min(mn, maxdis[mxdis]); mxx = max(mxx, maxdis[mxdis]); } if(mn >= mx) { mx3 = mx2; mx2 = mx; mx = mn; } else if(mn >= mx2) { mx3 = mx2; mx2 = mn; } else if(mn > mx3) { mx3 = mn; } } int ans = mxx; if(mx3!=-1) { ans = max(ans, mx3+mx2+L+L); } if(mx2!=-1) { ans = max(ans, mx+mx2+L); } return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         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...