| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 219609 |
2020-04-05T17:58:00 Z |
tatyam |
Islands (IOI08_islands) |
C++17 |
|
670 ms |
131076 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 0x1fffffffffffffff;
#define name3(a,b,c,d,...) d
#define rep1(a) for(ll i = 0; i < a; i++)
#define rep3(i,a,b) for(ll i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(a) for(ll i = a; i--; )
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
ll n, ans = 0;
vector<bool> used;
vector<vector<pll>> g;
ll Diameter(ll at){
unordered_map<ll, ll> cost;
cost[at] = 0;
vector<ll> q = {at};
while(q.size()){
ll at = q.back();
q.pop_back();
each(i, g[at]){
cost.try_emplace(i.first, INF);
if(chmin(cost[i.first], cost[at] + i.second)) q.push_back(i.first);
}
}
ll d1 = -1, max = 0;
each(i, cost) if(chmax(max, i.second)) d1 = i.first;
cost.clear();
cost[d1] = 0;
q = {d1};
while(q.size()){
ll at = q.back();
q.pop_back();
each(i, g[at]){
cost.try_emplace(i.first, INF);
if(chmin(cost[i.first], cost[at] + i.second)) q.push_back(i.first);
}
}
max = 0;
each(i, cost) chmax(max, i.second);
return max;
}
void solve(ll start){
if(used[start]) return;
vector<ll> list = {start};
used[start] = 1;
rep(list.size()){
ll at = list[i];
each(i, g[at]) if(!used[i.first]){
used[i.first] = 1;
list.push_back(i.first);
}
}
if(all_of(all(list), [](ll at){ return g[at].size() == 2; })){
ll min = INF;
each(at, list){
ans += g[at][0].second;
chmin(min, g[at][0].second);
}
ans -= min;
return;
}
unordered_map<ll, bool> is_circle;
ll at = start;
while(!is_circle.count(at)){
is_circle[at];
at = g[at][0].first;
}
ll circle_sum = 0, circle_cnt = 0;
while(!is_circle[at]){
is_circle[at] = 1;
circle_cnt++;
circle_sum += g[at][0].second;
at = g[at][0].first;
}
ll mx = 0;
ll dex = -1;
unordered_map<ll, ll> dp;
auto dfs = [&, s = at](ll from, ll at, auto f) -> void {
each(i, g[at]) if(i.first != from && i.first != s){
f(at, i.first, f);
if(!is_circle[i.first]){
chmax(dp[at], dp[i.first] + i.second);
if(chmax(mx, dp[at])) dex = at;
}
}
};
dfs(-1, at, dfs);
ll cnt = 0;
rep(circle_cnt){
ll to = g[at][0].first;
chmax(cnt, dp[at] + dp[to] + circle_sum - g[at][0].second);
at = to;
}
each(i, g[dex]) if(is_circle[i.first]){
pll e = i;
g[dex].erase(find(all(g[dex]), e));
g[e.first].erase(find(all(g[e.first]), pll{dex, e.second}));
chmax(cnt, Diameter(dex));
g[dex].insert(g[dex].begin(), e);
g[e.first].insert(g[e.first].begin(), pll{dex, e.second});
}
ans += cnt;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n;
used.resize(n);
g.resize(n);
rep(n){
ll a, b;
cin >> a >> b;
a--;
g[i].emplace_back(a, b);
}
rep(n) g[g[i][0].first].emplace_back(i, g[i][0].second);
rep(n) solve(i);
cout << ans << endl;
}
Compilation message
islands.cpp: In function 'void solve(ll)':
islands.cpp:7:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep1(a) for(ll i = 0; i < a; i++)
^
islands.cpp:6:28: note: in expansion of macro 'rep1'
#define name3(a,b,c,d,...) d
^
islands.cpp:9:18: note: in expansion of macro 'name3'
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
^~~~~
islands.cpp:53:5: note: in expansion of macro 'rep'
rep(list.size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
512 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2320 KB |
Output is correct |
| 2 |
Incorrect |
65 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
13256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
305 ms |
45704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
670 ms |
40668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
474 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
514 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
