oj.uz

Submission #240463

# Submission time Handle Problem Language Result Execution time Memory
240463 2020-06-19T16:54:55 Z c4ts0up Dreaming (IOI13_dreaming) C++14
0 / 100
 67 ms 25464 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;

const ll INF = 1e15;
const ll NMAX = 1e5+5;

struct Vertex {
	int id, parent;
	ll pdist;
	
	Vertex () {}
	Vertex (int x) { id = x; }
};

struct Graph {
	vector <Vertex> V;
	vector <pair <ll, int> > Adj[NMAX];
	vector <bool> vis;
	int excluded;
	
	Graph () {}
	Graph (int s) {
		V.resize(s);
		for (int i=0; i<s; i++) V[i] = Vertex(i);
	}
	
	// Hace una DFS y devuelve el nodo más lejano
	pair <ll,int> DFS(int o) {
		vector <ll> dist;
		stack <pair <int,int> > to;
		
		dist.resize(NMAX);
		for (int i=0; i<NMAX; i++) dist[i] = INF, vis[i] = false;
		
		to.push({0LL, o});
		dist[o] = 0;
		while (!to.empty()) {
			pair <int, ll> curr = to.top();
			to.pop();
			dist[curr.ss] = curr.ff;
			
			for (pair <ll, int> p : Adj[curr.ss]) {
				if (!vis[p.ss]) to.push({p.ff + curr.ff, p.ss}), V[p.ss].parent = curr.ss, V[p.ss].pdist = p.ff;
			}
		}
		
		// Encuentra el más lejano
		pair <ll, int> best = {-1, -1};
		for (int i=0; i<NMAX; i++) {
			// No pertence a esta componente
			if (!vis[i]) {
				excluded = i;
				continue;
			}
			
			best = max(best, {dist[i], i});
		}
		
		return best;
	}
	
	ll Diametro() {
		// Devuelve el diametro
		pair <ll, int> rx = DFS(0);
		pair <ll, int> ry = DFS(rx.ss);
		return ry.ff;
	}
	
	// Encuentra el radio. Devuele el centro
	int Radio(int o = 0) {
		pair <ll, int> rx = DFS(o);
		pair <ll, int> ry = DFS(rx.ss);
		
		int curr = ry.ss;
		int best = curr;
		ll a = ry.ff, b = 0;
		ll maxi = INF;
		
		
		while (curr != rx.ss) {
			if (max(a,b) < maxi) best = curr, maxi = max(a,b);
			
			a -= V[curr].pdist;
			b += V[curr].pdist;
			
			curr = V[curr].parent;
		}
		
		return best;
	}
};

Graph G;

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
	G = Graph(n);
	
	for (int i=0; i<m; i++) {
		G.Adj[A[i]].pb({T[i], B[i]});
		G.Adj[B[i]].pb({T[i], A[i]});
	}
	
	int g1 = G.Radio();
	int g2 = G.Radio(G.excluded);
	G.Adj[g2].pb({(ll)(l), g1});
	G.Adj[g1].pb({(ll)(l), g2});
	
	return G.Diametro();
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:20:8: warning: '<anonymous>.Graph::excluded' may be used uninitialized in this function [-Wmaybe-uninitialized]
 struct Graph {
        ^~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 25464 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 67 ms 25464 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 67 ms 25464 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 40 ms 19400 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 67 ms 25464 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 67 ms 25464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -