oj.uz

Submission #240509

# Submission time Handle Problem Language Result Execution time Memory
240509 2020-06-19T17:52:40 Z c4ts0up Dreaming (IOI13_dreaming) C++14
14 / 100
 106 ms 13744 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 = -1, sze;

	Graph () {}
	Graph (int s) {
        sze = s;
		V.resize(sze);
		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) {
	    //cerr << "Entrando a DFS..." << endl;
		vector <ll> dist;
		stack <pair <int,int> > to;

		dist.resize(sze);
		vis.resize(sze);
		for (int i=0; i<sze; i++) dist[i] = INF, vis[i] = false;

		// Hace la DFS
		to.push({0LL, o});
		dist[o] = 0;
		while (!to.empty()) {
			pair <int, ll> curr = to.top();
			//cerr << "Visitando " << curr.ss << " (distancia acc " << curr.ff << ")" << endl;
			to.pop();
			dist[curr.ss] = curr.ff;
			vis[curr.ss] = true;

			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<sze; i++) {
			// No pertence a esta componente
			if (!vis[i]) {
				excluded = i;
				continue;
			}

			if (dist[i] != 0) 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) {
	    //cerr << "--- PRIMERA DFS ---" << endl;
		pair <ll, int> rx = DFS(o);
		//cerr << "(" << rx.ff << ", " << rx.ss << ")" << endl;
		//cerr << "El excluido es " << excluded << endl;
        //cerr << "--- SEGUNDA DFS ---" << endl;
		pair <ll, int> ry = DFS(rx.ss);
		//cerr << "(" << ry.ff << ", " << ry.ss << ")" << endl;

		int curr = ry.ss;
		int best = curr;
		ll a = ry.ff, b = 0;
		ll maxi = INF;

        //cerr << "--- BUSCANDO RADIO ---" << endl;
		while (curr != rx.ss) {
            //cerr << "Revisando " << curr << endl;
			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);
	//cerr << "Creando grafo... OK" << endl;

	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]});
	}

	//cerr << "Llenando grafo... OK" << endl;

	int g1 = G.Radio();
	//cerr << "Primer centro " << g1 << endl;
	int g2 = G.Radio(G.excluded);
	//cerr << "Segundo centro " << g2 << endl;
	G.Adj[g2].pb({(ll)(l), g1});
	G.Adj[g1].pb({(ll)(l), g2});

	return G.Diametro();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13560 KB Output is correct
2 Correct 78 ms 13744 KB Output is correct
3 Correct 57 ms 10916 KB Output is correct
4 Correct 17 ms 6528 KB Output is correct
5 Correct 18 ms 6144 KB Output is correct
6 Correct 32 ms 7168 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 55 ms 9208 KB Output is correct
9 Correct 54 ms 10108 KB Output is correct
10 Correct 9 ms 5120 KB Output is correct
11 Correct 83 ms 12408 KB Output is correct
12 Correct 106 ms 13060 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13560 KB Output is correct
2 Correct 78 ms 13744 KB Output is correct
3 Correct 57 ms 10916 KB Output is correct
4 Correct 17 ms 6528 KB Output is correct
5 Correct 18 ms 6144 KB Output is correct
6 Correct 32 ms 7168 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 55 ms 9208 KB Output is correct
9 Correct 54 ms 10108 KB Output is correct
10 Correct 9 ms 5120 KB Output is correct
11 Correct 83 ms 12408 KB Output is correct
12 Correct 106 ms 13060 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct
14 Runtime error 13 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13560 KB Output is correct
2 Correct 78 ms 13744 KB Output is correct
3 Correct 57 ms 10916 KB Output is correct
4 Correct 17 ms 6528 KB Output is correct
5 Correct 18 ms 6144 KB Output is correct
6 Correct 32 ms 7168 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 55 ms 9208 KB Output is correct
9 Correct 54 ms 10108 KB Output is correct
10 Correct 9 ms 5120 KB Output is correct
11 Correct 83 ms 12408 KB Output is correct
12 Correct 106 ms 13060 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct
14 Runtime error 13 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 10020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13560 KB Output is correct
2 Correct 78 ms 13744 KB Output is correct
3 Correct 57 ms 10916 KB Output is correct
4 Correct 17 ms 6528 KB Output is correct
5 Correct 18 ms 6144 KB Output is correct
6 Correct 32 ms 7168 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 55 ms 9208 KB Output is correct
9 Correct 54 ms 10108 KB Output is correct
10 Correct 9 ms 5120 KB Output is correct
11 Correct 83 ms 12408 KB Output is correct
12 Correct 106 ms 13060 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct
14 Incorrect 8 ms 5120 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 13560 KB Output is correct
2 Correct 78 ms 13744 KB Output is correct
3 Correct 57 ms 10916 KB Output is correct
4 Correct 17 ms 6528 KB Output is correct
5 Correct 18 ms 6144 KB Output is correct
6 Correct 32 ms 7168 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 55 ms 9208 KB Output is correct
9 Correct 54 ms 10108 KB Output is correct
10 Correct 9 ms 5120 KB Output is correct
11 Correct 83 ms 12408 KB Output is correct
12 Correct 106 ms 13060 KB Output is correct
13 Correct 10 ms 5120 KB Output is correct
14 Runtime error 13 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -