| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 59487 |
2018-07-22T07:09:10 Z |
TAMREF |
Islands (IOI08_islands) |
C++11 |
|
1096 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];
int 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, Weic;
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;
}
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( Vei[i] + lsum );
lsum += ce[i];
Weic.push_back(Wei.back()); //copy
}
//Extract max 2 values in Wei in O(n) complexity
auto it = max_element(Wei.begin(),Wei.end());
ll MaxV = *it;
Wei.erase(it);
auto jt = max_element(Wei.begin(), Wei.end());
ll SndV = *jt;
//printf("clockwise MaxV, SndV = %lld, %lld\n",MaxV,SndV);
for(int i = 0; i < C; i++){
//printf("vertex : %d, own weight : %lld, clockwise weight : %lld\n",cv[i],Vei[i],Weic[i]-Vei[i]);
ll pV = (Weic[i] != MaxV ? MaxV : SndV);
ans = max(ans, 2LL * Vei[i] - Weic[i] + pV);
}
//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());
Wei.resize(C);
for(int i = 0; i < C; i++){
//printf("vertex : %d, Inc ew : %d\n",cv[i],ce[i]);
Wei[i] = Vei[i] + lsum;
lsum += ce[i];
Weic[i] = Wei[i];
}
//Extract max 2 values in Wei in O(n) complexity
it = max_element(Wei.begin(),Wei.end());
MaxV = *it;
Wei.erase(it);
jt = max_element(Wei.begin(), Wei.end());
SndV = *jt;
//printf("Inclockwise MaxV, SndV = %lld, %lld\n",MaxV,SndV);
for(int i = 0; i < C; i++){
//printf("vertex : %d, own weight : %lld, inclockwise weight : %lld\n",cv[i],Vei[i],Weic[i]-Vei[i]);
ll pV = (Weic[i] != MaxV ? MaxV : SndV);
ans = max(ans, 2LL * Vei[i] - Weic[i] + pV);
}
//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(){
FILE *fp = fopen("isl2.out","rt");
ll correct;
fscanf(fp,"%lld",&correct);
cout << "answer = " << correct << '\n';
}
int main(){
//freopen("isl2.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,0);
ans += dp_on_cycle();
}
}
cout << ans << '\n';
//debug();
}
Compilation message
islands.cpp: In function 'void debug()':
islands.cpp:154: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 |
27 ms |
23804 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
23912 KB |
Output isn't correct |
| 3 |
Incorrect |
25 ms |
23992 KB |
Output isn't correct |
| 4 |
Correct |
29 ms |
24164 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
24164 KB |
Output isn't correct |
| 6 |
Correct |
27 ms |
24164 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
24268 KB |
Output isn't correct |
| 8 |
Incorrect |
25 ms |
24268 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
24268 KB |
Output isn't correct |
| 10 |
Incorrect |
27 ms |
24268 KB |
Output isn't correct |
| 11 |
Correct |
24 ms |
24268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
24268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
24268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
25412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
30268 KB |
Output is correct |
| 2 |
Incorrect |
94 ms |
33592 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
162 ms |
41828 KB |
Output is correct |
| 2 |
Correct |
201 ms |
52820 KB |
Output is correct |
| 3 |
Incorrect |
239 ms |
67992 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
258 ms |
67992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
557 ms |
110360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1096 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 |
- |
