| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 629739 |
2022-08-15T02:23:47 Z |
dooompy |
Islands (IOI08_islands) |
C++17 |
|
992 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int to; ll cost; int idx;
};
vector<edge> adj[1000005];
bitset<1000005> seen, seenedge, inloop;
int par[1000005];
int cyclestart, cycleend;
void dfs(int node) {
seen[node] = true;
for (auto nxt : adj[node]) {
if (seenedge[nxt.idx]) continue;
seenedge[nxt.idx] = true;
if (seen[nxt.to]) {
// cycle found
cyclestart = node, cycleend = nxt.to;
} else {
par[nxt.to] = node;
dfs(nxt.to);
}
}
}
ll globmax = 0;
ll dfs_tree(int node, int par = -1) {
ll ans = 0;
for (auto nxt : adj[node]) {
if (nxt.to == par) continue;
if (inloop[nxt.to]) continue;
ll temp = dfs_tree(nxt.to, node);
globmax = max(globmax, ans + temp + nxt.cost);
ans = max(ans, temp + nxt.cost);
}
return ans;
}
int main() {
// freopen("isl.in", "r", stdin); freopen("isl.out", "w", stdout);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
int to; ll c; cin >> to >> c;
adj[i].push_back({to, c, i});
adj[to].push_back({i, c, i});
}
ll total = 0;
for (int i = 1; i <= n; i++) {
if (seen[i]) continue;
dfs(i);
vector<int> loop;
while (cyclestart != cycleend) {
loop.push_back(cyclestart);
cyclestart = par[cyclestart];
}
loop.push_back(cyclestart);
for (auto cur : loop) {
inloop[cur] = true;
}
ll ans = 0;
ll prevInMax = 0;
ll prevOutMax = 0;
map<int, ll> cursum;
ll totalsum = 0;
map<int, bool> seensecond;
for (int i = 0; i <= loop.size(); i++) {
if (i == 0) continue;
if (i == loop.size()) {
for (auto nxt : adj[loop[0]]) {
if (nxt.to == loop.back() && !seensecond[nxt.idx]) {
totalsum += nxt.cost;
break;
}
}
break;
}
for (auto nxt : adj[loop[i]]) {
if (nxt.to == loop[i-1] && !seensecond[nxt.idx]) {
seensecond[nxt.idx] = true;
cursum[loop[i]] += nxt.cost;
totalsum += nxt.cost;
break;
}
}
cursum[loop[i]] += cursum[loop[i-1]];
}
for (int i = 0; i < loop.size(); i++) {
globmax = 0;
ll tree = dfs_tree(loop[i]);
if (i > 0) {
ans = max({ans, tree + cursum[loop[i]] + prevInMax, totalsum + prevOutMax - cursum[loop[i]] + tree});
}
ans = max(ans, globmax);
prevInMax = max(prevInMax, tree - cursum[loop[i]]);
prevOutMax = max(prevOutMax, tree + cursum[loop[i]]);
}
total += ans;
}
cout << total << endl;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i <= loop.size(); i++) {
| ~~^~~~~~~~~~~~~~
islands.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | if (i == loop.size()) {
| ~~^~~~~~~~~~~~~~
islands.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int i = 0; i < loop.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23796 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 4 |
Correct |
12 ms |
23784 KB |
Output is correct |
| 5 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 6 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 7 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23804 KB |
Output is correct |
| 9 |
Correct |
14 ms |
23804 KB |
Output is correct |
| 10 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 11 |
Correct |
12 ms |
23764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23884 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
25196 KB |
Output is correct |
| 2 |
Correct |
69 ms |
28884 KB |
Output is correct |
| 3 |
Correct |
33 ms |
25308 KB |
Output is correct |
| 4 |
Correct |
20 ms |
24532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
30792 KB |
Output is correct |
| 2 |
Correct |
109 ms |
33952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
41056 KB |
Output is correct |
| 2 |
Correct |
309 ms |
52604 KB |
Output is correct |
| 3 |
Correct |
362 ms |
68548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
53788 KB |
Output is correct |
| 2 |
Correct |
561 ms |
94460 KB |
Output is correct |
| 3 |
Correct |
926 ms |
110000 KB |
Output is correct |
| 4 |
Runtime error |
722 ms |
131072 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
741 ms |
82656 KB |
Output is correct |
| 2 |
Runtime error |
992 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
797 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
