Submission #167389

#	Time	Username	Problem	Language	Result	Execution time	Memory
167389		DavidDamian	Dreaming (IOI13_dreaming)	C++11	47 / 100	105 ms	12644 KiB

dreaming

#include "dreaming.h"
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
///Diameter of a tree
///Determine the minimum longest path selecting optimal connections
struct edge
{
    int from,to;
    int w;
};
int color[100005];
int d[2][100005]; //Distance from node 1 and node 2
queue<int> Q;
vector<edge> adjList[100005];
int bfs(int s,int node,int c) ///Returns the farest node of s
{
    color[s]=c;
    d[node][s]=0;
    Q.push(s);
    int maximum=0;
    int max_Node=s;
    while(Q.size()){
        int u=Q.front();Q.pop();
        for(edge e: adjList[u]){
            int v=e.to;
            if(color[v]!=c){
                color[v]=c;
                d[node][v]=d[node][u]+e.w;
                if(d[node][v]>maximum){
                    maximum=d[node][v];
                    max_Node=v;
                }
                Q.push(v);
            }
        }
    }
    return max_Node;
}
int getMinimum_FarestDistance(int s,int c) ///Returns the minimum longest distance in a tree
{
    color[s]=c;
    Q.push(s);
    int minimum=1000000000;
    while(Q.size()){
        int u=Q.front();Q.pop();
        if(max(d[0][u],d[1][u]) < minimum){
            minimum=max(d[0][u],d[1][u]);
        }
        for(edge e: adjList[u]){
            int v=e.to;
            if(color[v]!=c){
                color[v]=c;
                Q.push(v);
            }
        }
    }
    return minimum;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;i++){
        edge e={A[i],B[i],T[i]};
        adjList[ A[i] ].push_back(e);
        swap(e.from,e.to);
        adjList[ B[i] ].push_back(e);
    }
    int c=1;
    int best[5];
    int j=0;
    int answer=0;
    for(int i=0;i<N;i++){
        if(color[i]!=0) continue;
        int u=bfs(i,0,c++); //Gets the farest node of i
        int v=bfs(u,1,c++); //Gets the farest node of u
        //u and v are the farest nodes between themselves in the tree
        answer=max(answer,d[1][v]);
        bfs(v,0,c++);
        best[j++]=getMinimum_FarestDistance(i,c);
    }
    int NewPath=best[0]+best[1]+L;
    answer=max(answer,NewPath);
    return answer;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23