| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 59529 |
2018-07-22T08:53:56 Z |
nhc7502 |
Islands (IOI08_islands) |
C++11 |
|
1961 ms |
132096 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pil = pair<int, ll>;
using pll = pair<ll, ll>;
using pili = pair<pil, int>;
using pli = pair<ll, int>;
#define X first
#define Y second
const int N = 1000005;
const ll INF = ll(1e18);
vector<pili> e[N];
int n, v[N], o[N], c, p[N], q[N];
vector<int> w;
vector<ll> d;
ll a[2 * N], b[2 * N], r, u[N];
void f(int x, int y){
if(q[x]){
p[c] = -1;
for(int i = c - 1; p[i + 1] != x; i--){
w.push_back(p[i]);
d.push_back(u[i]);
o[p[i]] = 1;
}
return;
}
if(v[x]) return;
v[x] = 1;
int r = 0;
for(pili i : e[x]){
if(i.Y == y) continue;
q[x] = 1;
p[c] = x;
u[c] = i.X.Y;
c++;
f(i.X.X, i.Y);
q[x] = 0;
c--;
}
}
ll g(int x, int p, ll &t){
pll r = {0, 0};
for(pili i : e[x]){
if(o[i.X.X] || i.X.X == p) continue;
ll z = g(i.X.X, x, t) + i.X.Y;
if(z >= r.X){ r.Y = r.X; r.X = z; }
else if(z > r.Y){ r.Y = z; }
}
t = max(t, r.X + r.Y);
return r.X;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int x; ll y;
scanf("%d%lld", &x, &y);
e[i].push_back(pili(pil(x, y), i));
e[x].push_back(pili(pil(i, y), i));
}
for(int i = 1; i <= n; i++){
if(v[i]) continue;
w.clear();
d.clear();
f(i, 0);
int s = w.size();
//for(int j = 0; j < s; j++) printf("aa %d %lld\n", w[j], d[j]);
ll t = 0;
for(int j = 0; j < s; j++){
a[j] = a[j + s] = g(w[j], 0, t);
b[j] = d[j] + (j ? b[j - 1] : 0);
}
for(int j = 0; j < s; j++) b[j + s] = b[j + s - 1] + d[j];
//for(int j = 0; j < 2 * s; j++) printf("bb %lld %lld\n", a[j], b[j]);
priority_queue<pli> lq, rq;
for(int j = 1; j < s; j++) rq.push({a[j] + b[j], j});
for(int j = 0, k = 0; j < s; j++){
while(k < j + s && b[k] - b[j] < b[j + s] - b[k]) k++;
//printf("jk %d %d\n", j, k);
while(!rq.empty() && rq.top().Y < k){
int x = rq.top().Y;
//printf("rq -> lq %lld %d\n", a[x] - b[x], x);
lq.push({a[x] - b[x], x});
rq.pop();
}
while(!lq.empty() && lq.top().Y <= j) lq.pop();
//if(!lq.empty()) printf("lq %lld\n", lq.top().X + b[j + s]);
//if(!rq.empty()) printf("rq %lld\n", rq.top().X - b[j]);
t = max(t, max((lq.empty() ? -INF : lq.top().X) + b[j + s],
(rq.empty() ? -INF : rq.top().X) - b[j]) + a[j]);
rq.push({a[j + s] + b[j + s], j + s});
//printf("rq push %lld %d\n", a[j + s] + b[j + s], j + s);
}
//printf("t %lld\n", t);
r += t;
}
printf("%lld\n", r);
}
Compilation message
islands.cpp: In function 'void f(int, int)':
islands.cpp:34:9: warning: unused variable 'r' [-Wunused-variable]
int r = 0;
^
islands.cpp: In function 'int main()':
islands.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
28 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
25 ms |
24124 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24124 KB |
Output is correct |
| 5 |
Correct |
26 ms |
24128 KB |
Output is correct |
| 6 |
Correct |
30 ms |
24152 KB |
Output is correct |
| 7 |
Correct |
28 ms |
24152 KB |
Output is correct |
| 8 |
Correct |
28 ms |
24152 KB |
Output is correct |
| 9 |
Correct |
29 ms |
24196 KB |
Output is correct |
| 10 |
Correct |
26 ms |
24196 KB |
Output is correct |
| 11 |
Correct |
26 ms |
24196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
24336 KB |
Output is correct |
| 2 |
Correct |
30 ms |
24336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
24368 KB |
Output is correct |
| 2 |
Correct |
31 ms |
24908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
26116 KB |
Output is correct |
| 2 |
Correct |
84 ms |
30020 KB |
Output is correct |
| 3 |
Correct |
57 ms |
30020 KB |
Output is correct |
| 4 |
Correct |
39 ms |
30020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
33160 KB |
Output is correct |
| 2 |
Correct |
92 ms |
38184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
48400 KB |
Output is correct |
| 2 |
Correct |
261 ms |
61424 KB |
Output is correct |
| 3 |
Correct |
254 ms |
79444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
327 ms |
79444 KB |
Output is correct |
| 2 |
Correct |
493 ms |
114484 KB |
Output is correct |
| 3 |
Runtime error |
836 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. |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
515 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. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1961 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. |
| 2 |
Halted |
0 ms |
0 KB |
- |
