| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125105 |
2019-07-04T15:36:12 Z |
NMAC427 |
Islands (IOI08_islands) |
C++17 |
|
1108 ms |
131076 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.ff);
}
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 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 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";
ans += compAns;
}
cout << ans << "\n";
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:126: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 |
3 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
380 KB |
Output isn't correct |
| 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 |
Incorrect |
17 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
130 ms |
4640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
194 ms |
13456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1108 ms |
26884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
356 ms |
48156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
424 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
