| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 84727 |
2018-11-17T03:57:04 Z |
updown1 |
Islands (IOI08_islands) |
C++17 |
|
1401 ms |
132096 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=1000000;
///500,000,000
int N, comp[MAXN], cat, nonn[MAXN], st[MAXN], nd[MAXN];
ll siz[MAXN], out, ns[MAXN], pre1[MAXN], pre2[MAXN], suf1[MAXN], suf2[MAXN], ans[MAXN];
bool vis[MAXN], cyc[MAXN];
queue<int> next1;
vector<pair<int, int> > adj[MAXN]; /// (node, cost)
void go(int at) {
if (comp[at] != -1) return;
comp[at] = cat;
for (auto i: adj[at]) go(i.a);
}
void calc_size(int at) {
if (vis[at]) return;
vis[at] = true;
if (adj[at].size() == 1) return;
ll b1 = 0, b2 = 0;
for (auto i: adj[at]) if (!cyc[i.a] && !vis[i.a]) {
calc_size(i.a);
siz[at] = max(siz[at], i.b+siz[i.a]);
if (siz[i.a]+i.b >= b1) {b2 = b1; b1 = i.b+siz[i.a];}
else if (siz[i.a]+i.b > b2) {b2 = i.b+siz[i.a];}
}
//w<< at+1 c b1 s b2<<e;
ans[comp[at]] = max(ans[comp[at]], b1+b2);
}
ll solve (int x) {
ll ret = 0;
int loc = 0; int at = st[x];
//w<< "comp" s x <<e;
while (at != st[x] || loc == 0) {
//w<< at+1<<e;
ns[loc] = siz[at];
vis[at] = true;
bool found = false;
for (auto i: adj[at]) if (!vis[i.a]) {
nd[loc] = i.b;
at = i.a;
found = true;
break;
}
if (!found) {
vis[st[x]] = false;
for (auto i: adj[at]) if (!vis[i.a]) {
nd[loc] = i.b;
at = i.a;
}
}
loc++;
}
if (loc == 1) {while (true){}}
assert(loc != 1); /// edge from x to x
//For (i, 0, loc) w<< ns[i] s nd[i]<<e;
pre1[0] = ns[0];
ll curr = 0;
For (i, 1, loc) {
curr += nd[i-1];
pre1[i] = max(pre1[i-1], curr+ns[i]);
ret = max(ret, curr+ns[0] + ns[i]);
}
//For (i, 0, loc) w<< "pre1" s i c pre1[i]<<e;
suf1[loc-1] = nd[loc-1] + ns[loc-1];
curr = nd[loc-1];
for (int i=loc-2; i>=1; i--) {
curr += nd[i];
suf1[i] = max(suf1[i+1], curr+ns[i]);
}
//For (i, 0, loc) w<< "suf1" s i c suf1[i]<<e;
For (i, 0, loc-1) ret = max(ret, pre1[i] + suf1[i+1]);
//w<< "from pass 1, ret =" s ret<<e;
pre2[0] = ns[0];
For (i, 1, loc) pre2[i] = max(pre2[i-1]+nd[i-1], ns[i]);
//For (i, 0, loc) w<< "pre2" s i c pre2[i]<<e;
suf2[loc-1] = 0;
for (int i=loc-2; i>=0; i--) suf2[i] = max(suf2[i+1]+nd[i], ns[i+1]+nd[i]);
//For (i, 0, loc) w<< "suf2" s i c suf2[i]<<e;
For (i, 0, loc) ret = max(ret, pre2[i]+suf2[i]);
//w<< "after pass 2, ret =" s ret<<e;
return max(ret, ans[x]);
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
ffi {cyc[i] = true; comp[i] = -1; int b, d; cin >> b >> d; b--; if (i != b) {adj[i].pb(mp(b, d)); adj[b].pb(mp(i, d));}}
ffi if (comp[i] == -1) {go(i); cat++;}
ffi if (adj[i].size() == 1) next1.push(i);
while (!next1.empty()) {
int at = next1.front(); next1.pop();
if (!cyc[at]) continue;
if (nonn[at] == adj[at].size()-1) {
cyc[at] = false;
for (auto i: adj[at]) {
nonn[i.a]++;
if (cyc[i.a]) next1.push(i.a);
}
}
}
//ffi w<< i+1 c cyc[i]<<e;
ffi if (cyc[i]) {st[comp[i]] = i; calc_size(i);}
//ffi w<< i+1 c siz[i]<<e;
ffi {
vis[i] = false;
if (!cyc[i]) vis[i] = true;
}
For (i, 0, cat) out += solve(i);
w<< out <<e;
}
Compilation message
islands.cpp:101:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
islands.cpp: In function 'int main()':
islands.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (nonn[at] == adj[at].size()-1) {
~~~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23900 KB |
Output is correct |
| 2 |
Correct |
23 ms |
23936 KB |
Output is correct |
| 3 |
Correct |
24 ms |
24024 KB |
Output is correct |
| 4 |
Correct |
23 ms |
24024 KB |
Output is correct |
| 5 |
Correct |
23 ms |
24040 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24040 KB |
Output is correct |
| 7 |
Correct |
22 ms |
24100 KB |
Output is correct |
| 8 |
Correct |
22 ms |
24144 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24160 KB |
Output is correct |
| 10 |
Correct |
23 ms |
24272 KB |
Output is correct |
| 11 |
Correct |
23 ms |
24272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
24272 KB |
Output is correct |
| 2 |
Correct |
26 ms |
24288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
24340 KB |
Output is correct |
| 2 |
Correct |
32 ms |
24600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
25240 KB |
Output is correct |
| 2 |
Correct |
45 ms |
27880 KB |
Output is correct |
| 3 |
Correct |
36 ms |
27880 KB |
Output is correct |
| 4 |
Correct |
29 ms |
27880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
29548 KB |
Output is correct |
| 2 |
Correct |
68 ms |
33020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
39332 KB |
Output is correct |
| 2 |
Correct |
135 ms |
44024 KB |
Output is correct |
| 3 |
Correct |
164 ms |
57780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
220 ms |
57780 KB |
Output is correct |
| 2 |
Correct |
284 ms |
81788 KB |
Output is correct |
| 3 |
Correct |
310 ms |
86460 KB |
Output is correct |
| 4 |
Correct |
398 ms |
117928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
423 ms |
117928 KB |
Output is correct |
| 2 |
Runtime error |
1401 ms |
132096 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
621 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
