oj.uz

Submission #172010

# Submission time Handle Problem Language Result Execution time Memory
172010 2019-12-30T19:09:13 Z DavidDamian Islands (IOI08_islands) C++11
40 / 100
 2000 ms 131076 KB 
#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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 29 ms 23928 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 23 ms 23848 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 27 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 24 ms 23800 KB Output is correct
11 Correct 28 ms 23928 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24056 KB Output is correct
2 Correct 662 ms 24452 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1762 ms 25464 KB Output is correct
2 Execution timed out 2067 ms 28408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 30068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 42344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 51316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 110012 KB Output is correct
2 Runtime error 752 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 517 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -