oj.uz

Submission #76578

# Submission time Handle Problem Language Result Execution time Memory
76578 2018-09-14T21:59:35 Z Shafin666 Dreaming (IOI13_dreaming) C++14
0 / 100
 74 ms 10772 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 10772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 10772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 10772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 9364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 10772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 10772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -