oj.uz

Submission #172248

# Submission time Handle Problem Language Result Execution time Memory
172248 2019-12-31T21:40:38 Z DavidDamian Islands (IOI08_islands) C++11
80 / 100
 681 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll A[1000006];
int heapSize=0;
int leftNode(int i)
{
    return i*2;
}
int rightNode(int i)
{
    return i*2+1;
}
int parent(int i)
{
    return i/2;
}
void maxHeapify(int i)
{
    int L=leftNode(i);
    int R=rightNode(i);
    int best;
    if(L<=heapSize && A[L]>A[i])
        best=L;
    else
        best=i;
    if(R<=heapSize && A[R]>A[best])
        best=R;
    if(best!=i){
        swap(A[i],A[best]);
        maxHeapify(best);
    }
}
void increaseKey(int i,ll key)
{
    if(A[i]>key) return;
    A[i]=key;
    while(i>1 && A[i]>A[parent(i)]){
        swap(A[i],A[parent(i)]);
        i=parent(i);
    }
}
void heapInsert(ll x)
{
    A[++heapSize]=-LLONG_MAX;
    increaseKey(heapSize,x);
}
ll extractMax()
{
    ll maximum=A[1];
    A[1]=A[heapSize--];
    maxHeapify(1);
    return maximum;
}
ll viewMax()
{
    return A[1];
}
struct edge{
    int from,to;
    int w;
    int id;
};
int n;
int color[1000006];
int p[1000006];
int id[1000006];
int weight[1000006];
ll sumCycle;
vector<edge> eCycle;
vector<int> cycle;
vector<edge> adjList[1000006];
void dfsVisit(int u)
{
    color[u]=1;
    for(edge e: adjList[u]){
        int v=e.to;
        if(id[u]==e.id) continue;
        if(color[v]==0){
            id[v]=e.id;
            p[v]=u;
            weight[v]=e.w;
            dfsVisit(v);
        }
        else if(color[v]==1){ //Cycle
            edge x=e;
            swap(x.from,x.to);
            eCycle.push_back(x);
            swap(x.from,x.to);
            while(x.from!=v){
                x.to=p[x.from];
                x.id=id[x.from];
                x.w=weight[x.from];
                eCycle.push_back(x);
                x.from=x.to;
            }
        }
    }
    color[u]=-1;
}
queue<int> Q;
ll d[1000006];
ll longest[1000006];
ll SL[1000006];
int c=1;
ll diameter(int root)
{
    d[root]=0;
    color[root]=c;
    Q.push(root);
    ll maximum=0;
    int node=root;
    while(Q.size()){
        int u=Q.front();
        Q.pop();
        for(edge e: adjList[u]){
            int v=e.to;
            if(v==0) continue;
            if(color[v]!=c){
                color[v]=c;
                d[v]=d[u]+(ll)e.w;
                if(d[v]>maximum){
                    maximum=d[v];
                    node=v;
                }
                Q.push(v);
            }
        }
    }
    longest[root]=maximum;
    maximum=0;
    d[node]=0;
    Q.push(node);
    c++;
    color[node]=c;
    while(Q.size()){
        int u=Q.front();
        Q.pop();
        for(edge e: adjList[u]){
            int v=e.to;
            if(v==0) continue;
            if(color[v]!=c){
                color[v]=c;
                d[v]=d[u]+(ll)e.w;
                if(d[v]>maximum){
                    maximum=d[v];
                    node=v;
                }
                Q.push(v);
            }
        }
    }
    return maximum;
}
ll maxPath(int root)
{
    ll maximum=0;
    sumCycle=0;
    int i=0;
    for(edge e: eCycle){
        cycle.push_back(e.from);
        sumCycle+=(ll)e.w;
        SL[e.to]=SL[e.from]+(ll)e.w;
    }
    SL[cycle[0]]=0;
    int C=cycle.size();
    ++c;
    for(int i=0;i<cycle.size();i++){
        int u=cycle[i];
        int a=cycle[(i-1+C)%C];
        int b=cycle[(i+1)%C];
        for(int j=0;j<adjList[u].size();j++){
            if(adjList[u][j].to==a || adjList[u][j].to==b) adjList[u][j].to=0;
        }
        maximum=max(maximum,diameter(u)); //Gets the diameter of the tree rooted at u
    }
    //The maximum is given by selecting all pairs i,j of nodes in the cycle
    //The sum of the longest path in tree rooted at i and tree rooted at j
    //And the maxPath in the cycle between i and j
    //ans= max (max _i<j_ {(longest[i]-SL[i])+(longest[j]+SL[j])},
    //           sumCycle max _i<j_ {(longest[i]+SL[i])+(longest[j]-SL[j])} )
    for(int j=1;j<cycle.size();j++){
        ll a=longest[ cycle[j-1] ]-SL[ cycle[j-1] ]; //Inserts term i
        heapInsert(a);
        a=viewMax(); //Gets the maximum for all the pasts terms i
        ll b=longest[ cycle[j] ]+SL[ cycle[j] ]; //Term j
        maximum=max(maximum,a+b);
    }
    while(heapSize) extractMax();
    for(int j=1;j<cycle.size();j++){
        ll a=longest[ cycle[j-1] ]+SL[ cycle[j-1] ]; //Inserts term i
        heapInsert(a);
        a=viewMax(); //Gets the maximum for all the past terms i
        ll b=longest[ cycle[j] ]-SL[ cycle[j] ]; //Term j
        maximum=max(maximum,sumCycle+a+b);
    }
    while(heapSize) extractMax();
    return maximum;
}
ll total=0;
void dfs()
{
    for(int i=1;i<=n;i++){
        if(color[i]==0){
            dfsVisit(i);
            total+=maxPath(i);
            cycle.clear();
            eCycle.clear();
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        int b;
        cin>>a>>b;
        edge e;
        e.from=i;
        e.to=a;
        e.w=b;
        e.id=i;
        adjList[e.from].push_back(e);
        swap(e.from,e.to);
        adjList[e.from].push_back(e);
    }
    dfs();
    cout<<total<<'\n';
    return 0;
}

Compilation message

islands.cpp: In function 'll maxPath(int)':
islands.cpp:168:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cycle.size();i++){
                 ~^~~~~~~~~~~~~
islands.cpp:172:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<adjList[u].size();j++){
                     ~^~~~~~~~~~~~~~~~~~
islands.cpp:182:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=1;j<cycle.size();j++){
                 ~^~~~~~~~~~~~~
islands.cpp:190:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=1;j<cycle.size();j++){
                 ~^~~~~~~~~~~~~
islands.cpp:159:9: warning: unused variable 'i' [-Wunused-variable]
     int i=0;
         ^

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23900 KB Output is correct
7 Correct 23 ms 23804 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 23 ms 23932 KB Output is correct
11 Correct 23 ms 23928 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24060 KB Output is correct
2 Correct 24 ms 24056 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24056 KB Output is correct
2 Correct 27 ms 24440 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25620 KB Output is correct
2 Correct 54 ms 28916 KB Output is correct
3 Correct 39 ms 25848 KB Output is correct
4 Correct 32 ms 24824 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 30708 KB Output is correct
2 Correct 85 ms 35028 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 44168 KB Output is correct
2 Correct 182 ms 51016 KB Output is correct
3 Correct 215 ms 63968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 61536 KB Output is correct
2 Correct 358 ms 91692 KB Output is correct
3 Correct 464 ms 103004 KB Output is correct
4 Correct 512 ms 131072 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 98548 KB Output is correct
2 Runtime error 681 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 493 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -