| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53762 |
2018-07-01T06:59:00 Z |
강한남자킹현수(#2036) |
Islands (IOI08_islands) |
C++11 |
|
1678 ms |
233344 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 |
22 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23912 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23980 KB |
Output is correct |
| 4 |
Correct |
21 ms |
23980 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23984 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24040 KB |
Output is correct |
| 7 |
Correct |
23 ms |
24204 KB |
Output is correct |
| 8 |
Correct |
23 ms |
24204 KB |
Output is correct |
| 9 |
Correct |
23 ms |
24204 KB |
Output is correct |
| 10 |
Correct |
21 ms |
24204 KB |
Output is correct |
| 11 |
Correct |
24 ms |
24204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
24204 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
24300 KB |
Output is correct |
| 2 |
Correct |
25 ms |
24792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
25724 KB |
Output is correct |
| 2 |
Correct |
52 ms |
29180 KB |
Output is correct |
| 3 |
Correct |
38 ms |
29180 KB |
Output is correct |
| 4 |
Correct |
38 ms |
29180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
31348 KB |
Output is correct |
| 2 |
Correct |
79 ms |
35192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
42584 KB |
Output is correct |
| 2 |
Correct |
257 ms |
53584 KB |
Output is correct |
| 3 |
Correct |
202 ms |
67928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
67928 KB |
Output is correct |
| 2 |
Correct |
324 ms |
92132 KB |
Output is correct |
| 3 |
Correct |
502 ms |
114828 KB |
Output is correct |
| 4 |
Correct |
454 ms |
131528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
428 ms |
131528 KB |
Output is correct |
| 2 |
Correct |
1349 ms |
165852 KB |
Output is correct |
| 3 |
Correct |
549 ms |
165852 KB |
Output is correct |
| 4 |
Correct |
722 ms |
165852 KB |
Output is correct |
| 5 |
Correct |
646 ms |
165852 KB |
Output is correct |
| 6 |
Correct |
1629 ms |
165852 KB |
Output is correct |
| 7 |
Correct |
739 ms |
197964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
618 ms |
197964 KB |
Output is correct |
| 2 |
Correct |
574 ms |
197964 KB |
Output is correct |
| 3 |
Correct |
869 ms |
233344 KB |
Output is correct |
| 4 |
Correct |
796 ms |
233344 KB |
Output is correct |
| 5 |
Correct |
631 ms |
233344 KB |
Output is correct |
| 6 |
Correct |
660 ms |
233344 KB |
Output is correct |
| 7 |
Correct |
1678 ms |
233344 KB |
Output is correct |
