| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 125098 |
2019-07-04T15:21:09 Z |
NMAC427 |
Islands (IOI08_islands) |
C++17 |
|
565 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.ss >= max1) {
max2 = max1;
max1 = childDFS.ff;
} else if (childDFS.ss > 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);
vector<int> __cycle;
for (int i = 0; i < N; i++) {
if (visited[i]) continue;
__cycle.clear();
queue<int> q;
q.push(i);
while (!q.empty()) {
auto front = q.front();
q.pop();
__cycle.push_back(front);
if (visited[front]) {
bool __inCycle = false;
for (auto v: __cycle) {
if (to[i].ff == v) __inCycle = true;
if (__inCycle) inCycle[v] = true;
}
continue;
}
visited[front] = true;
q.push(to[front].ff);
}
}
// Solve
int ans = 0;
for (int i = 0; i < N; i++) {
if (!inCycle[i]) continue;
int compAns = 0;
int next = i;
vector<int> cycle;
vector<int> dfsV;
vector<int> prefixSum = {0};
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:132: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 |
Runtime error |
267 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 4 |
Runtime error |
116 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
| 8 |
Runtime error |
263 ms |
131072 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Incorrect |
3 ms |
376 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 |
Runtime error |
141 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 |
273 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 |
445 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 |
320 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 |
565 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 |
471 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 |
Incorrect |
405 ms |
47844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
527 ms |
131076 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
