| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 59521 |
2018-07-22T08:33:38 Z |
TAMREF |
Islands (IOI08_islands) |
C++11 |
|
2000 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];
bool vis[mx];
bool dE[mx];
int n;
vector<int> cv; //cycle vertex
vector<int> ce; //cycle edge weight
vector<ll> Vei, Wei, Weic;
int dfs_cnt;
int dfs(int x){
++dfs_cnt;
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.push_back(E[e].w);
}else{
dE[e] = 1;
tcyc = dfs(u);
cyc |= tcyc;
if(tcyc){
ce.push_back(E[e].w);
}
}
}
if(cyc){
//printf("push %d in cv\n",x);
cv.push_back(x);
}
if(cyc == x){
//printf("stopping cycle in %d\n",x);
cyc = 0;
}
return cyc;
}
ll lans;
ll dfs_st(int x){ //dfs for each subtrees in cycle
++dfs_cnt;
vis[x] = 0;
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) + 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(vector<ll>& Vw, vector<int>& E, vector<ll>& sE){
deque<pli> dq;
int m = E.size();
ll lsum = E[0];
ll ret = 0;
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 = cv.size();
ll lsum = 0;
ll ans = 0;
//give cycle-vertices their own number
rotate(ce.begin(),ce.begin()+1,ce.end()); //f**k
for(int i = 0; i < C; i++){
vis[cv[i]] = 0;
//printf("vertex : %d, clockwise - edge : %d\n",cv[i],ce[i]);
}
//clockwise
for(int i = 0; i < C; i++){
Vei.push_back( dfs_st(cv[i]) );
Wei.push_back( lsum );
lsum += ce[i];
}
lans = 0;
ans = max(ans, calc(Vei, ce, Wei));
ans = max(ans, lans);
//inclockwise - reversing all the vectors
lsum = 0;
reverse(cv.begin(),cv.end());
reverse(Vei.begin(),Vei.end());
reverse(ce.begin(), ce.end() - 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));
//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);
}
}
}
*/
printf("n = %d, dfs_cnt = %d\n",n,dfs_cnt);
FILE *fp = fopen(S,"rt");
ll correct;
fscanf(fp,"%lld",&correct);
cout << "answer = " << correct << '\n';
}
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]){
cv.clear();
ce.clear();
Wei.clear();
Vei.clear();
Weic.clear();
dfs(i);
ans += dp_on_cycle();
}
}
cout << ans << '\n';
//debug("isl19g.out");
}
Compilation message
islands.cpp: In function 'void debug(const char*)':
islands.cpp:172: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 |
Runtime error |
57 ms |
47612 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
56 ms |
47800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
70 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Correct |
28 ms |
48120 KB |
Output is correct |
| 5 |
Runtime error |
60 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
52 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
54 ms |
48120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
57 ms |
48288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
65 ms |
48288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
51 ms |
48300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
62 ms |
48300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
61 ms |
48344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
48416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
49964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
53940 KB |
Output is correct |
| 2 |
Runtime error |
101 ms |
60888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
69236 KB |
Output is correct |
| 2 |
Correct |
282 ms |
78004 KB |
Output is correct |
| 3 |
Correct |
358 ms |
89040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
102788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1340 ms |
132096 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2057 ms |
132096 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
