| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 156956 | 2019-10-08T14:19:45 Z | farmersrice | Islands (IOI08_islands) | C++17 | 376 ms | 131072 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 2000013
#define INF 1000000000000000000LL
#define MOD 1000000007LL
#define IINF 1000000000
#define mp make_pair
#define pb push_back
#define remove pop
#define all(x) x.begin(), x.end()
int n, m;
vector<int> adj[MAXN];
vector<pair2> adjDist[MAXN];
int seen[MAXN];
int par[MAXN];
int dist[MAXN];
bool inCycle[MAXN];
ll depth[MAXN];
ll reldist[MAXN]; //relative distances to 0 node in cycle
vector<int> cycleNodes;
bool cycle;
ll cycleLength;
void getCycle(int cur, int par = -1) {
if (cycle) return;
cycleNodes.pb(cur);
seen[cur] = true;
for (pair2 p : adjDist[cur]) {
if (p.first == par) continue;
cycleLength += p.second;
if (seen[p.first]) {
cycle = true;
return;
}
getCycle(p.first, cur);
if (cycle) return;
cycleLength -= p.second;
}
cycleNodes.pop_back();
}
void getDepth(int cur, int original, int par = -1, ll curDist = 0) {
depth[original] = max(depth[original], curDist);
for (pair2 p : adjDist[cur]) {
int next = p.first;
if (next == par) continue;
if (inCycle[next]) continue;
ll nextDist = p.second;
getDepth(next, original, cur, curDist + nextDist);
}
}
void getReldist(int cur, ll curDist = 0, int index = 0) {
if (index >= cycleNodes.size()) return;
reldist[index] = curDist;
if (index == ((int)cycleNodes.size()) - 1) return;
for (pair2 p : adjDist[cur]) {
if (p.first != cycleNodes[index + 1]) continue;
getReldist(p.first, curDist + p.second, index + 1);
}
}
int main() {
if (fopen("FILENAME.in", "r")) {
freopen("FILENAME.in", "r", stdin);
freopen("FILENAME.out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int u, v, l;
cin >> v >> l; u=i;v--;
adj[u].pb(v);
adj[v].pb(u);
adjDist[u].pb(mp(v, l));
adjDist[v].pb(mp(u, l));
}
//cout << "tha fucc " << endl;
getCycle(0);
for (int i : cycleNodes) {
inCycle[i] = true;
}
for (int i : cycleNodes) {
getDepth(i, i);
}
vector<int> paddedCycle = cycleNodes;
for (int i : cycleNodes) {
paddedCycle.pb(i);
}
getReldist(cycleNodes[0]);
multiset<ll> dists;
for (int i = 0; i < cycleNodes.size(); i++) {
dists.insert(depth[cycleNodes[i]] - reldist[i]);
}
//cout << "cycle length is " << cycleLength << endl;
ll answer = INF;
for (int i = (int) cycleNodes.size(); i < paddedCycle.size(); i++) {
int corr = i - (int)cycleNodes.size();
//Remove corr from the multiset
dists.erase(dists.find(depth[cycleNodes[corr]] - reldist[corr]));
ll best = *(--dists.end());
answer = min(answer, best + depth[cycleNodes[corr]] + cycleLength + reldist[corr]);
dists.insert(depth[cycleNodes[corr]] - reldist[corr] - cycleLength);
}
cout << answer << endl;
}
//GCD GCD GCD USE GCD IN MATH
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 219 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Incorrect | 91 ms | 94328 KB | Output isn't correct |
| 3 | Incorrect | 90 ms | 94328 KB | Output isn't correct |
| 4 | Incorrect | 90 ms | 94456 KB | Output isn't correct |
| 5 | Incorrect | 91 ms | 94316 KB | Output isn't correct |
| 6 | Incorrect | 107 ms | 94328 KB | Output isn't correct |
| 7 | Runtime error | 217 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Incorrect | 90 ms | 94328 KB | Output isn't correct |
| 9 | Runtime error | 227 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Incorrect | 91 ms | 94332 KB | Output isn't correct |
| 11 | Runtime error | 223 ms | 131072 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 91 ms | 94456 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 93 ms | 94584 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 102 ms | 95716 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 143 ms | 101604 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 234 ms | 115676 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 309 ms | 128692 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 292 ms | 131072 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 | 376 ms | 131072 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |