Submission #240528

#	Time	Username	Problem	Language	Result	Execution time	Memory
240528		c4ts0up	Dreaming (IOI13_dreaming)	C++17	100 / 100	331 ms	19268 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
/*
ID: c4ts0up
LANG: C++
TASK: dreaming
*/

using namespace std;

const ll INF = 1e10;
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;
	vector <ll> dist;
	int sze;

	Graph () {}
	Graph (int s) {
        sze = s;
		V.resize(sze);
		vis.resize(sze);
		dist.resize(sze);
		for (int i=0; i<sze; i++) V[i] = Vertex(i), vis[i] = false, dist[i] = INF;
	}

	// Hace una DFS y devuelve el nodo más lejano
	pair <ll,int> DFS(int o) {
	    ////cerr << "Entrando a DFS..." << endl;
		stack <pair <int,int> > to;
		unordered_set <int> seen;

		// 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;
			seen.insert(curr.ss);

			for (pair <ll, int> p : Adj[curr.ss]) {
                // es diferente al padre
				if (!seen.count(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 = {0, o};
		for (int i : seen) {
			if (dist[i] != 0) best = max(best, {dist[i], i});
		}

		// Colorea los nodos ya vistos
		for (int i : seen) vis[i] = true;

		return best;
	}

	ll Diametro() {
		// Devuelve el diametro
		pair <ll, int> rx = DFS(0);
		//cerr << "Primer viaje de diametro : (" << rx.ff << ", " << rx.ss << ")" << endl;
		pair <ll, int> ry = DFS(rx.ss);
		//cerr << "Segundo viaje de diametro : (" << ry.ff << ", " << ry.ss << ")" << endl;
		return ry.ff;
	}

	// Encuentra el radio. Devuele {radio, nodo}
	pair <ll, int> Radio(int o) {
	    //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 {(maxi == INF ? 0 : maxi), best};
	}
};

Graph G;

int travelTime(int n, int m, int largo, 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;

	pair <ll, int> bigc = {0, 0};
	vector <int> centros;

	for (int i=0; i<n; i++) {
	    // Componente nueva
        if (!G.vis[i]) {
            //cerr << "Investigando el componente con " << i;
            pair <ll, int> res = G.Radio(i);
            //cerr << " --> (" << res.ff << ", " << res.ss << ")" << endl;
            // Puede ser el super radio... ?
            if (res > bigc) bigc = res;
            centros.push_back(res.ss);
        }
    }

    //cerr << "El BC es " << bigc.ss << endl;

    for (int c : centros) {
        // El mismo
        if (c == bigc.ss) continue;
        G.Adj[c].pb({(ll)(largo), bigc.ss});
        G.Adj[bigc.ss].pb({(ll)(largo), c});
    }

	return G.Diametro();
}

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