Submission #520211

#TimeUsernameProblemLanguageResultExecution timeMemory
520211sofapudenIslands (IOI08_islands)C++14
27 / 100
1036 ms131076 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mx = 0, bes = 0; vector<vector<array<ll,2>>> gr; vector<int> vis; void dfs(int x, set<int> &s, ll dis){ vis[x] = 1; s.insert(x); if(dis > mx){ mx = dis; bes = x; } for(auto y : gr[x]){ if(!s.count(y[0]))dfs(y[0],s,dis+y[1]); } s.erase(x); } int main() { int n; cin >> n; gr.resize(n); vis.resize(n,0); for(int i = 0; i < n; ++i){ ll a, b; cin >> a >> b; a--; gr[i].push_back({a,b}); gr[a].push_back({i,b}); } ll ans = 0; for(int i = 0; i < n; ++i){ if(!vis[i]){ mx = 0; set<int> s; dfs(i,s,0); dfs(bes,s,0); dfs(bes,s,0); ans+=mx; } } cout << ans << '\n'; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...