Submission #172249

#	Time	Username	Problem	Language	Result	Execution time	Memory
172249		DavidDamian	Islands (IOI08_islands)	C++11	80 / 100	682 ms	131076 KiB

islands

#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;
    }
    eCycle.clear();
    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();
        }
    }
}
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 (stderr)

islands.cpp: In function 'll maxPath(int)':
islands.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cycle.size();i++){
                 ~^~~~~~~~~~~~~
islands.cpp:173:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<adjList[u].size();j++){
                     ~^~~~~~~~~~~~~~~~~~
islands.cpp:183:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=1;j<cycle.size();j++){
                 ~^~~~~~~~~~~~~
islands.cpp:191: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 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10