Submission #172010

#	Time	Username	Problem	Language	Result	Execution time	Memory
172010		DavidDamian	Islands (IOI08_islands)	C++11	40 / 100	2067 ms	131076 KiB

islands

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;
struct edge{
    int from,to;
    ll w;
};
vector<edge> adjList[1000006];
int color[1000006];
int p[1000006];
int weight[1000006];
vector<edge> cycle;
void dfsVisit(int u)
{
    color[u]=1;
    for(edge e: adjList[u]){
        int v=e.to;
        if(v==p[u] && e.w==weight[u]) continue;
        if(color[v]==0){
            p[v]=u;
            weight[v]=e.w;
            dfsVisit(v);
        }
        else if(color[v]==1){ //Cycle
            edge x=e;
            swap(x.from,x.to);
            cycle.push_back(x);
            swap(x.from,x.to);
            while(x.from!=v){
                x.to=p[x.from];
                x.w=weight[x.from];
                cycle.push_back(x);
                x.from=x.to;
            }
        }
    }
    color[u]=-1;
}
queue<int> Q;
ll d[1000006];
int c=1;
ll diameter(int r)
{
    color[r]=c;
    d[r]=0;
    Q.push(r);
    ll maximum=0;
    int node=r;
    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]+e.w;
                if(d[v]>maximum && v!=0){
                    maximum=d[v];
                    node=v;
                }
                Q.push(v);
            }
        }
    }
    color[node]=++c;
    d[node]=0;
    maximum=0;
    Q.push(node);
    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]+e.w;
                if(d[v]>maximum){
                    maximum=d[v];
                    node=v;
                }
                Q.push(v);
            }
        }
    }
    ll ans=d[node];
    return ans;
}
ll total=0;
ll maxPath(int root)
{
    ll maximum=0;
    for(edge e: cycle){

        int u=e.from,v=e.to;
        int id1=0,id2=0;
        for(int i=0;i<adjList[u].size();i++){
            if(adjList[u][i].to==v && adjList[u][i].w==e.w){
                id1=i;
                adjList[u][i].to=0;
                break;
            }
        }
        for(int i=0;i<adjList[v].size();i++){
            if(adjList[v][i].to==u && adjList[v][i].w==e.w){
                id2=i;
                adjList[v][i].to=0;
                break;
            }
        }
        ++c;
        maximum=max(maximum,diameter(root));
        adjList[u][id1].to=v;
        adjList[v][id2].to=u;
    }
    maximum=max(maximum,diameter(root));
    return maximum;
}
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;
        ll b;
        cin>>a>>b;
        edge e;
        e.from=i;
        e.to=a;
        e.w=b;
        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:99:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<adjList[u].size();i++){
                     ~^~~~~~~~~~~~~~~~~~
islands.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<adjList[v].size();i++){
                     ~^~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10