Submission #875413

#TimeUsernameProblemLanguageResultExecution timeMemory
875413AverageAmogusEnjoyerDreaming (IOI13_dreaming)C++17
Compilation error
0 ms0 KiB
#include "bits/stdc++.h" #include "dreaming.h" using namespace std; using ll = long long; template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; } template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; } const int N=1e5; vector<pair<int,int>> adj[N]; int dp[N],dp2[N]; bool done[N]; vector<int> cc; void getCC(int u,int e) { cc.push_back(u); for (auto &[v,len]: adj[u]) if (v!=e) { getCC(v,u); } } void dfs(int u,int e) { for (auto &[v,len]: adj[u]) if (v!=e) { dfs(v,u); cmax(dp[u],dp[v]+len); } } void dfs2(int u,int e) { multiset<int> lengths; lengths.insert(dp2[u]); for (auto &[v,len]: adj[u]) if (v!=e) { lengths.insert(dp[v]+len); } for (auto &[v,len]: adj[u]) if (v!=e) { lengths.erase(lengths.find(dp[v]+len)); assert(!lengths.empty()); dp2[v]=*lengths.rbegin()+len; dfs2(v,u); lengths.insert(dp[v]+len); } } int travelTime(int n, int m, int k, int u[], int v[], int len[]) { for (int i=0;i<m;i++) { adj[u[i]].emplace_back(v[i],len[i]); adj[v[i]].emplace_back(u[i],len[i]); } vector<int> diams; const int inf = 1e9; for (int i=0;i<n;i++) { if (!done[i]) { cc.clear(); getCC(i,-1); for (int &j: cc) { assert(!done[j]); done[j]=true; } dfs(i,-1); dfs2(i,-1); int rs=inf; for (int &j: cc) { cmin(rs,max(dp[j],dp2[j])); } diams.push_back(rs); // dp[u] = max dist in subtree of u, // dp2[u] = max dist in everything except subtree of u } } sort(diams.begin(),diams.end()); n = int(diams.size()); if (diams.size()==1) { return diams[0]; } else if (diams.size()==2) { return diams[0]+diams[1]+k; } else { return max(diams[n-1]+diams[n-2]+k,diams[n-2]+diams[n-3]+2*k); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,m,k; cin >> n >> m >> k; int u[m],v[m],len[m]; for (int i=0;i<m;i++) { cin >> u[i] >> v[i] >> len[i]; } cout << travelTime(n,m,k,u,v,len) << "\n"; }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc5wjtMr.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchan6Kq.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status