Submission #76578

#	Time	Username	Problem	Language	Result	Execution time	Memory
76578		Shafin666	Dreaming (IOI13_dreaming)	C++14	0 / 100	74 ms	10772 KiB

dreaming

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

const int MAX_N = 1e3+10;
vector<int> adj[MAX_N], R;
int V[MAX_N], visited[MAX_N], w[MAX_N][MAX_N];
int ecc[MAX_N];


int dfs(int u, int par) {
	visited[u] = 1; int i, mn = ecc[u];
	//if(adj[u].size() == 1) return ecc[u];

	for(i = 0;  i < adj[u].size(); i++) if(adj[u][i] != par && !visited[adj[u][i]]) mn = min(mn, dfs(adj[u][i], u));

	return mn;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int i, j, k, sum = 0;
    int ans;
    
    for(i = 0; i < N; i++) for(j = 0; j < N; j++) w[i][j] = 1e9+7;
    memset(ecc, 0, sizeof(ecc));

    for(i = 0; i < M; i++) {
    	adj[A[i]].push_back(B[i]);
    	adj[B[i]].push_back(A[i]);

    	w[A[i]][B[i]] = w[B[i]][A[i]] = T[i];
    } 
    for(k = 0; k < N; k++) {
    	for(i = 0; i < N; i++) {
    		for(j = 0; j < N; j++)
    			w[i][j] =  min(w[i][j], w[i][k] + w[k][j]);
    	}
    }

    for(i = 0; i < N; i++) {
    	for(j = 0; j < N; j++)
    		if(w[i][j] != 1e9+7 && i != j) ecc[i] = max(ecc[i], w[i][j]);
    }

    for(i = 0; i < N; i++) {
    	if(!visited[i]) R.push_back(dfs(i, i));
    } sort(R.begin(), R.end(), greater<int>());

    return R[0]+R[1]+L;
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs(int, int)':
dreaming.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0;  i < adj[u].size(); i++) if(adj[u][i] != par && !visited[adj[u][i]]) mn = min(mn, dfs(adj[u][i], u));
              ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:21:18: warning: unused variable 'sum' [-Wunused-variable]
     int i, j, k, sum = 0;
                  ^~~
dreaming.cpp:22:9: warning: unused variable 'ans' [-Wunused-variable]
     int ans;
         ^~~

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