Submission #139243

#	Time	Username	Problem	Language	Result	Execution time	Memory
139243		MrBrionix	Dreaming (IOI13_dreaming)	C++14	100 / 100	206 ms	22644 KiB

dreaming

#include <stdio.h>
#include <stdlib.h>
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;


vector<int> grafo[100005],peso[100005],v,dist;
int part,best,tmp,ans,sum;
bool vis[100005];

void dfs1(int nodo,int val,int last){
    
    //cout<<nodo<<" "<<val<<endl;
    
    if(val>best){
        best=val;
        part=nodo;
    }
    
    for(int i=0;i<grafo[nodo].size();i++){
        if(grafo[nodo][i]!=last){
            dfs1(grafo[nodo][i],val+peso[nodo][i],nodo);
        }
    }
    
}

bool dfs2(int nodo,int last){
    
    if(nodo==part)return true;
    
    for(int i=0;i<grafo[nodo].size();i++){
        
        if(grafo[nodo][i]!=last){
            if(dfs2(grafo[nodo][i],nodo)==true){
                v.push_back(peso[nodo][i]);
                return true;   
            }
        }
        
    }
    
    return false;
}

void dfs(int nodo){
    vis[nodo]=true;
    for(int i=0;i<grafo[nodo].size();i++){
        if(vis[grafo[nodo][i]]==false)
            dfs(grafo[nodo][i]);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    for(int i=0;i<M;i++){
        grafo[A[i]].push_back(B[i]);
        grafo[B[i]].push_back(A[i]);
        peso[A[i]].push_back(T[i]);
        peso[B[i]].push_back(T[i]);
    }
    
    for(int i=0;i<N;i++){
        if(vis[i]==false){
            best=0;
            part=i;
            dfs1(i,0,-1);
            
            best=0;
            tmp=part;
            dfs1(part,0,-1);
            
            v.clear();
            dfs2(tmp,-1);
            dfs(i);
            
            ans=max(ans,best);
            sum=0;
            
            int tmp2=best;
            for(int j=0;j<v.size();j++){
                sum+=v[j];
                tmp2=min(tmp2,max(sum,best-sum));
            }
            
            dist.push_back(tmp2);
            //cout<<best<<" edasd "<<tmp2<<endl;
        }
    }
    
    sort(dist.begin(),dist.end());
    
    if(dist.size()>=2)
    ans=max(ans,dist[dist.size()-1]+dist[dist.size()-2]+L);
    
    if(dist.size()>=3)
    ans=max(ans,dist[dist.size()-3]+dist[dist.size()-2]+2*L);
    
    return ans;
}


/*


#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main() {
	int N, M, L, i;
	int res;

	FILE *f = fopen("input.txt", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d%d%d", &N, &M, &L);
	for (i = 0; i < M; i++)
		res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
	fclose(f);

	int answer = travelTime(N, M, L, A, B, T);
	printf("%d\n", answer);

	return 0;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int, int)':
dreaming.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'bool dfs2(int, int)':
dreaming.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[nodo].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:82:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<v.size();j++){
                         ~^~~~~~~~~

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