oj.uz

Submission #59479

# Submission time Handle Problem Language Result Execution time Memory
59479 2018-07-22T06:31:18 Z TAMREF Islands (IOI08_islands) C++11
6 / 100
 1520 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 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, u;
    vis[x] = 1;
    for(int &e : G[x]){
        if(e == nume) continue;
        u = E[e].oppo(x);
        if(vis[u]){
            cyc = 1;
            ce.push_back(E[e].w);
        }else{
            if(dfs(u,e)){
                cyc = 1;
                ce.push_back(E[e].w);
            }
        }
    }
    if(cyc) cv.push_back(x);
    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
    for(int i = 0; i < C; i++){
        vis[cv[i]] = ++num_cyc;
    }
    //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());
    reverse(ce.begin(), ce.end());
    rotate(ce.begin(),ce.begin()+1,ce.end());
    Wei.resize(C);

    for(int i = 0; i < C; 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);
    }
}

int main(){
    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';
}

Subtask #1
6.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23800 KB Output is correct
2 Incorrect 25 ms 24168 KB Output isn't correct
3 Incorrect 26 ms 24168 KB Output isn't correct
4 Incorrect 27 ms 24168 KB Output isn't correct
5 Incorrect 26 ms 24168 KB Output isn't correct
6 Incorrect 27 ms 24168 KB Output isn't correct
7 Incorrect 25 ms 24168 KB Output isn't correct
8 Incorrect 24 ms 24168 KB Output isn't correct
9 Incorrect 26 ms 24168 KB Output isn't correct
10 Incorrect 26 ms 24168 KB Output isn't correct
11 Correct 27 ms 24168 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 24168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 24168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 25344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 30024 KB Output is correct
2 Incorrect 78 ms 33284 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 41000 KB Output is correct
2 Correct 234 ms 51760 KB Output is correct
3 Incorrect 203 ms 66940 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 66940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 514 ms 106492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1520 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 -