| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53745 |
2018-07-01T06:27:50 Z |
강한남자킹현수(#2036) |
Islands (IOI08_islands) |
C++11 |
|
606 ms |
153052 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pil = pair<int, 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 r = 0;
for(pili i : e[x]){
if(o[i.X.X] || i.X.X == p) continue;
r = max(r, g(i.X.X, x) + i.X.Y);
}
return r;
}
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]);
for(int j = 0; j < s; j++){
a[j] = a[j + s] = g(w[j], 0);
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]);
ll t = 0;
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:33:9: warning: unused variable 'r' [-Wunused-variable]
int r = 0;
^
islands.cpp: In function 'int main()':
islands.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
islands.cpp:59: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 |
22 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23908 KB |
Output isn't correct |
| 3 |
Correct |
21 ms |
23984 KB |
Output is correct |
| 4 |
Correct |
22 ms |
24000 KB |
Output is correct |
| 5 |
Correct |
21 ms |
24024 KB |
Output is correct |
| 6 |
Correct |
21 ms |
24180 KB |
Output is correct |
| 7 |
Correct |
21 ms |
24180 KB |
Output is correct |
| 8 |
Correct |
23 ms |
24180 KB |
Output is correct |
| 9 |
Correct |
21 ms |
24180 KB |
Output is correct |
| 10 |
Incorrect |
25 ms |
24180 KB |
Output isn't correct |
| 11 |
Correct |
21 ms |
24180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
24300 KB |
Output is correct |
| 2 |
Correct |
22 ms |
24300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
24300 KB |
Output is correct |
| 2 |
Correct |
24 ms |
24684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
25708 KB |
Output is correct |
| 2 |
Correct |
66 ms |
29160 KB |
Output is correct |
| 3 |
Correct |
45 ms |
29160 KB |
Output is correct |
| 4 |
Incorrect |
28 ms |
29160 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
31320 KB |
Output is correct |
| 2 |
Correct |
80 ms |
35168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
42612 KB |
Output is correct |
| 2 |
Correct |
188 ms |
53548 KB |
Output is correct |
| 3 |
Correct |
218 ms |
67904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
244 ms |
67904 KB |
Output is correct |
| 2 |
Correct |
309 ms |
91948 KB |
Output is correct |
| 3 |
Correct |
516 ms |
114832 KB |
Output is correct |
| 4 |
Correct |
531 ms |
131484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
441 ms |
131484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
606 ms |
153052 KB |
Output is correct |
| 2 |
Incorrect |
569 ms |
153052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
