| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 59528 |
2018-07-22T08:49:12 Z |
TAMREF |
Islands (IOI08_islands) |
C++11 |
|
1644 ms |
132096 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int mx = 1e6 + 5;
struct Edg{
int u, v, w;
inline int oppo(int x){
return u + v - x;
}
} E[mx];
vector<int> G[mx];
int vis[mx];
bool dE[mx];
int num_cyc = 1; //greater than 1
int n;
int cv[mx], n_cv; //cycle vertex
int ce[mx], n_ce; //cycle edge weight
ll Vei[mx], n_vei;
ll Wei[mx], n_wei;
int dfs(int x){
int cyc = 0, tcyc, u;
vis[x] = 1;
for(int &e : G[x]){
if(dE[e]) continue;
u = E[e].oppo(x);
if(vis[u]){
//printf("cycle detected - (%d->%d)\n",x,u);
cyc = u;
dE[e] = 1;
ce[n_ce++] = E[e].w;
}else{
dE[e] = 1;
tcyc = dfs(u);
cyc |= tcyc;
if(tcyc){
ce[n_ce++] = E[e].w;
}
}
}
if(cyc){
//printf("push %d in cv\n",x);
cv[n_cv++] = x;
}
if(cyc == x){
//printf("stopping cycle in %d\n",x);
cyc = 0;
}
return cyc;
}
ll lans;
ll dfs_st(int x, int c){ //dfs for each subtrees in cycle
vis[x] = c;
int u, w;
ll ans = 0, ans2 = 0, tmp;
for(int &e : G[x]){
u = E[e].oppo(x);
w = E[e].w;
if(vis[u] == 1){
tmp = dfs_st(u, c) + w;
if(tmp > ans) ans2 = ans, ans = tmp;
else ans2 = max(ans2, tmp);
}
}
lans = max(lans, ans + ans2); //local answer in subtree
return ans;
}
inline void BackInsert(deque<pli>& d, pli p){
while(!d.empty() && d.back() <= p) d.pop_back();
d.push_back(p);
}
inline void OldPop(deque<pli>& d, int k){
while(!d.empty() && d.front().second < k) d.pop_front();
}
ll calc(ll *Vw, int *E, ll *sE, int m){
deque<pli> dq;
ll lsum = E[0];
ll ret = 0;
for(int i = 0; i < m; i++){
//printf("Vw = %lld, E = %d, sE = %lld\n",Vw[i],E[i],sE[i]);
}
for(int i = 1; i < m; i++){
BackInsert(dq, pli(Vw[i] + sE[i], i));
lsum += E[i];
}
for(int i = 0; i < m; i++){
OldPop(dq, i+1);
ret = max(ret, Vw[i] - sE[i] + dq.front().first);
BackInsert(dq, pli(Vw[i] + lsum + sE[i], i+m));
}
dq.clear();
dq.shrink_to_fit();
return ret;
}
ll dp_on_cycle(){
int C = n_cv;
ll lsum = 0;
ll ans = 0;
//give cycle-vertices their own number
rotate(ce, ce+1, ce+C); //f**k
for(int i = 0; i < C; i++){
vis[cv[i]] = ++num_cyc;
//printf("vertex : %d, clockwise - edge : %d\n",cv[i],ce[i]);
}
//clockwise
for(int i = 0; i < C; i++){
Vei[n_vei++] = dfs_st(cv[i], vis[cv[i]]);
Wei[n_wei++] = lsum;
lsum += ce[i];
}
ans = max(ans, calc(Vei, ce, Wei, n_ce));
//inclockwise - reversing all the vectors
lsum = 0;
reverse(cv, cv + n_cv);
reverse(Vei, Vei + n_vei);
reverse(ce, ce + n_ce - 1);
for(int i = 0; i < C; i++){
//printf("vertex : %d, Inc ew : %d\n",cv[i],ce[i]);
Wei[i] = lsum;
lsum += ce[i];
}
ans = max(ans, calc(Vei, ce, Wei, n_ce));
ans = max(ans, lans);
//printf("dp result : %lld\n",ans);
return ans;
}
void input(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> E[i].v >> E[i].w;
E[i].u = i;
G[i].push_back(i);
G[E[i].v].push_back(i);
}
}
void debug(const char* S){
/*
for(int i = 1; i <= n; i++){
if(G[i].size() > 1){
//printf("deg[%d] = %d\n",i,G[i].size());
for(int &e : G[i]){
if(E[e].w > 90000000)
//printf("(%d, %d)\n",E[e].oppo(i),E[e].w);
}
}
}
*/
FILE *fp = fopen(S,"rt");
ll correct;
fscanf(fp,"%lld",&correct);
printf("answer = %lld\n",correct);
}
int main(){
//freopen("isl19g.in","rt",stdin);
ios_base::sync_with_stdio(false);cin.tie(0);
ll ans = 0;
input();
for(int i = 1; i <= n; i++){
if(!vis[i]){
n_cv = n_ce = n_wei = n_vei = 0;
dfs(i);
lans = 0;
ans += dp_on_cycle();
}
}
cout << ans << '\n';
//debug("isl19g.out");
}
Compilation message
islands.cpp: In function 'void debug(const char*)':
islands.cpp:170:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fp,"%lld",&correct);
~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
28 ms |
23912 KB |
Output is correct |
| 3 |
Correct |
30 ms |
23992 KB |
Output is correct |
| 4 |
Correct |
29 ms |
23992 KB |
Output is correct |
| 5 |
Correct |
26 ms |
24084 KB |
Output is correct |
| 6 |
Correct |
29 ms |
24084 KB |
Output is correct |
| 7 |
Correct |
29 ms |
24096 KB |
Output is correct |
| 8 |
Correct |
28 ms |
24100 KB |
Output is correct |
| 9 |
Correct |
25 ms |
24132 KB |
Output is correct |
| 10 |
Correct |
25 ms |
24156 KB |
Output is correct |
| 11 |
Correct |
25 ms |
24216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
24220 KB |
Output is correct |
| 2 |
Correct |
30 ms |
24232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
24380 KB |
Output is correct |
| 2 |
Correct |
31 ms |
24536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
25492 KB |
Output is correct |
| 2 |
Correct |
57 ms |
27604 KB |
Output is correct |
| 3 |
Correct |
44 ms |
27604 KB |
Output is correct |
| 4 |
Correct |
31 ms |
27604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
29992 KB |
Output is correct |
| 2 |
Correct |
90 ms |
33364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
40868 KB |
Output is correct |
| 2 |
Correct |
220 ms |
48376 KB |
Output is correct |
| 3 |
Correct |
206 ms |
58456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
61376 KB |
Output is correct |
| 2 |
Correct |
372 ms |
84872 KB |
Output is correct |
| 3 |
Correct |
514 ms |
99228 KB |
Output is correct |
| 4 |
Correct |
510 ms |
119504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
483 ms |
129016 KB |
Output is correct |
| 2 |
Runtime error |
1644 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 |
1068 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 |
- |
