| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 59505 |
2018-07-22T07:49:09 Z |
TAMREF |
Islands (IOI08_islands) |
C++11 |
|
989 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;
vector<int> cv; //cycle vertex
vector<ll> ce; //cycle edge weight
vector<ll> Vei, Wei;
int dfs(int x, int nume){
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,e);
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 dfs_st(int x, int c){ //dfs for each subtrees in cycle
vis[x] = c;
int u, w;
ll ans = 0;
for(int &e : G[x]){
u = E[e].oppo(x);
w = E[e].w;
if(vis[u] == 1){
ans = max(ans, dfs_st(u, c) + w);
}
}
return ans;
}
pli dq[2 * mx];
int dq_f, dq_r;
inline void BackInsert(pli p){
assert(dq_f < 2 * mx);
while(dq_f != dq_r && dq[dq_r] <= p) --dq_r;
dq[dq_r++] = p;
}
inline void OldPop(int k){
while(dq_f != dq_r && dq[dq_f].second < k) ++dq_f;
}
ll calc(vector<ll>& Vw, vector<ll>& E, vector<ll>& sE){
dq_f = dq_r = 0;
int m = E.size();
ll lsum = E[0];
ll ret = 0;
for(int i = 1; i < m; i++){
BackInsert(pli(Vw[i] + sE[i], i));
lsum += E[i];
}
for(int i = 0; i < m; i++){
OldPop(i+1);
ret = max(ret, Vw[i] - sE[i] + dq[dq_f].first);
BackInsert(pli(Vw[i] + lsum + sE[i], i+m));
}
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]] = ++num_cyc;
//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], vis[cv[i]]) );
Wei.push_back( lsum );
lsum += ce[i]; //copy
}
ans = max(ans, calc(Vei, ce, Wei));
//inclockwise - reversing all the vectors
lsum = 0;
reverse(cv.begin(),cv.end());
reverse(Vei.begin(),Vei.end());
if(C > 2) reverse(ce.begin(), ce.end() - 1);
else reverse(ce.begin(), ce.end());
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;
cv.reserve(n);
ce.reserve(n);
Wei.reserve(n);
Vei.reserve(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(){
FILE *fp = fopen("isl19f.out","rt");
ll correct;
fscanf(fp,"%lld",&correct);
cout << "answer = " << correct << '\n';
}
int main(){
//freopen("isl19f.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();
dfs(i,0);
ans += dp_on_cycle();
}
}
cout << ans << '\n';
//debug();
}
Compilation message
islands.cpp: In function 'void debug()':
islands.cpp:160: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 |
25 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23916 KB |
Output isn't correct |
| 3 |
Correct |
24 ms |
23952 KB |
Output is correct |
| 4 |
Correct |
23 ms |
23976 KB |
Output is correct |
| 5 |
Correct |
23 ms |
23976 KB |
Output is correct |
| 6 |
Correct |
24 ms |
23976 KB |
Output is correct |
| 7 |
Correct |
24 ms |
23976 KB |
Output is correct |
| 8 |
Correct |
27 ms |
24180 KB |
Output is correct |
| 9 |
Correct |
27 ms |
24180 KB |
Output is correct |
| 10 |
Incorrect |
24 ms |
24180 KB |
Output isn't correct |
| 11 |
Correct |
24 ms |
24180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
24272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
24272 KB |
Output is correct |
| 2 |
Correct |
29 ms |
24616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
25372 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
28068 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
30044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
39912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
54292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
422 ms |
100740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
989 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 |
- |
