# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53881 |
2018-07-01T13:50:01 Z |
baactree |
Islands (IOI08_islands) |
C++17 |
|
1432 ms |
158448 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<pair<int,int> > adj[1000005];
int trip[1000005], w[1000005];
bool chk[1000005];
vector<ll> cycle;
vector<int> len;
ll dd[1000005], a[2000005];
int vn;
int dfs(int now, int pi) {
int ret = trip[now] = ++vn;
for (auto &e : adj[now]) {
if (e.second==pi)continue;
if (!trip[e.first]) {
ret=min(ret,dfs(e.first, e.second));
}
else if(!chk[e.first]){
ret = min(ret, trip[e.first]);
cycle.push_back(e.first);
chk[e.first] = true;
len.push_back(w[e.second]);
}
}
if (ret < trip[now]) {
chk[now] = true;
cycle.push_back(now);
len.push_back(w[pi]);
}
return ret;
}
ll val;
void dfs2(int now) {
chk[now] = true;
for (auto &e : adj[now]) {
if (chk[e.first])continue;
dfs2(e.first);
val = max(val, dd[now] + dd[e.first] + w[e.second]);
dd[now] = max(dd[now], dd[e.first] + w[e.second]);
}
}
ll calc(vector<ll> &d, vector<int> &len, int m) {
deque<int> dq;
ll sum = len[0];
for (int i = 1; i < m * 2; i++) {
a[i] = sum + d[i%m];
sum += len[i%m];
}
ll ret = 0;
sum = 0;
int ri;
ri = 0;
for (int i = 0; i < m; i++) {
for (int j = ri; j < i + m; j++) {
while (!dq.empty() && a[dq.back()] <= a[j])dq.pop_back();
dq.push_back(j);
}
ri = i + m;
while (!dq.empty() && dq.front() <= i)dq.pop_front();
ll temp = d[i] + a[dq.front()] - sum;
ret = max(ret, temp);
sum += len[i];
}
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
adj[i].emplace_back(a,i);
adj[a].emplace_back(i,i);
w[i] = b;
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (!trip[i]) {
cycle.clear();
len.clear();
dfs(i, 0);
int m = cycle.size();
val = 0;
for (int i = 0; i < cycle.size(); i++) {
dfs2(cycle[i]);
cycle[i] = dd[cycle[i]];
}
val = max(val,calc(cycle, len, m));
reverse(len.begin(), len.end() - 1);
reverse(cycle.begin(), cycle.end());
val = max(val, calc(cycle, len, m));
ans += val;
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cycle.size(); i++) {
~~^~~~~~~~~~~~~~
islands.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
23940 KB |
Output is correct |
3 |
Correct |
24 ms |
23984 KB |
Output is correct |
4 |
Correct |
21 ms |
24036 KB |
Output is correct |
5 |
Correct |
20 ms |
24036 KB |
Output is correct |
6 |
Correct |
21 ms |
24112 KB |
Output is correct |
7 |
Correct |
21 ms |
24112 KB |
Output is correct |
8 |
Correct |
20 ms |
24112 KB |
Output is correct |
9 |
Correct |
21 ms |
24112 KB |
Output is correct |
10 |
Correct |
24 ms |
24112 KB |
Output is correct |
11 |
Correct |
24 ms |
24112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
24208 KB |
Output is correct |
2 |
Correct |
24 ms |
24208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
24208 KB |
Output is correct |
2 |
Correct |
23 ms |
24556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
25088 KB |
Output is correct |
2 |
Correct |
45 ms |
27520 KB |
Output is correct |
3 |
Correct |
36 ms |
27520 KB |
Output is correct |
4 |
Correct |
27 ms |
27520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
28792 KB |
Output is correct |
2 |
Correct |
72 ms |
30964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
36880 KB |
Output is correct |
2 |
Correct |
130 ms |
41460 KB |
Output is correct |
3 |
Correct |
164 ms |
52236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
52236 KB |
Output is correct |
2 |
Correct |
276 ms |
70400 KB |
Output is correct |
3 |
Correct |
297 ms |
73580 KB |
Output is correct |
4 |
Correct |
373 ms |
95712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
482 ms |
95712 KB |
Output is correct |
2 |
Correct |
1153 ms |
121456 KB |
Output is correct |
3 |
Correct |
408 ms |
121456 KB |
Output is correct |
4 |
Correct |
535 ms |
121456 KB |
Output is correct |
5 |
Correct |
528 ms |
121456 KB |
Output is correct |
6 |
Correct |
1432 ms |
121456 KB |
Output is correct |
7 |
Correct |
563 ms |
135808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
566 ms |
135808 KB |
Output is correct |
2 |
Correct |
537 ms |
135808 KB |
Output is correct |
3 |
Correct |
617 ms |
158448 KB |
Output is correct |
4 |
Correct |
722 ms |
158448 KB |
Output is correct |
5 |
Correct |
516 ms |
158448 KB |
Output is correct |
6 |
Correct |
497 ms |
158448 KB |
Output is correct |
7 |
Correct |
1418 ms |
158448 KB |
Output is correct |