| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125109 |
2019-07-04T15:51:07 Z |
NMAC427 |
Islands (IOI08_islands) |
C++17 |
|
422 ms |
131072 KB |
// https://oj.uz/problem/view/IOI08_islands
#include <bits/stdc++.h>
#define coutV(v) for (auto e: v) {cerr << e << " ";} cerr << "\n"
#define int int64_t
#define ff first
#define ss second
using namespace std;
int N;
vector<pair<int, int>> to;
vector<vector<int>> from;
vector<bool> inCycle;
pair<int, int> dfsSolve(int v) {
int max1 = 0;
int max2 = 0;
int maxInternal = 0; // Maximum internal path;
for (const int child: from[v]) {
if (inCycle[child]) continue; // Check here because we want to be able to pass in a node of the cycle
auto childDFS = dfsSolve(child);
childDFS.ff += to[child].ss;
if (childDFS.ff >= max1) {
max2 = max1;
max1 = childDFS.ff;
} else if (childDFS.ff > max2) {
max2 = childDFS.ff;
}
maxInternal = max(maxInternal, childDFS.ss);
}
maxInternal = max(maxInternal, max1 + max2);
return {max1, maxInternal};
}
signed main() {
#ifndef __APPLE__
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> N;
to.resize(N);
from.resize(N);
for (int i = 0; i < N; i++) {
cin >> to[i].ff >> to[i].ss;
to[i].ff -= 1;
from[to[i].ff].push_back(i);
}
// Generate inCycle Vector
inCycle.assign(N, false);
vector<bool> visited (N, false);
for (int i = 0; i < N; i++) {
if (visited[i]) continue;
vector<int> cycle;
int next = i;
while (true) {
visited[next] = true;
cycle.push_back(next);
if (visited[to[next].ff]) {
bool __inCycle = false;
for (int v: cycle) {
if (to[next].ff == v) __inCycle = true;
if (__inCycle) inCycle[v] = true;
}
break;
} else {
next = to[next].ff;
}
}
}
// Solve
int ans = 0;
for (int i = 0; i < N; i++) {
if (!inCycle[i]) continue;
int compAns = 0;
vector<int> cycle;
vector<int> dfsV;
vector<int> prefixSum = {0};
int next = i;
do {
auto dfs = dfsSolve(next);
compAns = max(compAns, dfs.ss); // Internal Path
cycle.push_back(next);
dfsV.push_back(dfs.ff);
prefixSum.push_back(prefixSum.back() + to[next].ss);
next = to[next].ff;
} while (next != i);
for (int v: cycle) {
inCycle[v] = false; // Don't visit same component twice
}
coutV(cycle);
int _compAns = compAns;
int tmm = dfsV[0] - prefixSum[0];
int tp = dfsV[0] + prefixSum[0];
for(int i = 1; i < cycle.size(); i++) {
compAns = max(compAns, dfsV[i] + prefixSum[i] + tmm);
compAns = max(compAns, dfsV[i] - prefixSum[i] + tp + prefixSum.back());
tmm = max(tmm, dfsV[i] - prefixSum[i]);
tp = max(tp, dfsV[i] + prefixSum[i]);
}
int __compAns = compAns;
compAns = _compAns;
int leftPtr = 0;
int rightPtr = 1;
int diameter = cycle.size();
int prefix = dfsV[0] + to[i].ss;
while (leftPtr < diameter && rightPtr < diameter * 2) {
// cerr << leftPtr << " " << rightPtr << "\n";
if (leftPtr == (rightPtr % diameter)) {
prefix -= dfsV[leftPtr];
prefix -= to[cycle[leftPtr]].ss;
leftPtr++;
}
compAns = max(compAns, prefix + dfsV[rightPtr % diameter]);
if (prefix <= dfsV[rightPtr % diameter]) {
prefix = dfsV[rightPtr % diameter];
leftPtr = rightPtr % diameter;
}
prefix += to[cycle[rightPtr % diameter]].ss;
rightPtr += 1;
}
cerr << "CompAns = " << compAns << "\n";
cerr << "-----------------\n";
assert(compAns == __compAns);
ans += compAns;
}
cout << ans << "\n";
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < cycle.size(); i++) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
2424 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
8020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
13424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
268 ms |
51636 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
357 ms |
47844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
422 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
