제출 #1311823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311823		dimitri.shengelia	Dreaming (IOI13_dreaming)	C++20	100 / 100	102 ms	9380 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

int n, m, d1;
vector <vector <pair <int, int>>> adj;

vector <int> v;
vector <bool> visited;
vector <int> d;
vector <int> diameter;

int mx, mxd;
int answer;

void bfs( int i ) {

	queue <int> q;
	q.push( i );

	v.push_back( i );

	visited[i] = true;

	while ( !q.empty() ) {

		int x = q.front();
		q.pop();

		for ( auto y : adj[x] ) {

			if ( visited[y.first] == false ) {

				visited[y.first] = true;

				q.push( y.first );

			}

		}

	}

	return;

}

int median( int i ) {

	int answer1;

	int start, end, dist;

	queue <int> q;
	q.push( i );

	d[i] = 0;

	start = i;

	vector <int> w;

	while ( !q.empty() ) {

		int x = q.front();
		q.pop();

		w.push_back( x );

		for ( auto y : adj[x] ) {

			if ( d[y.first] == -1 ) {

				d[y.first] = d[x] + y.second;

				q.push( y.first );

			}

		}

		if ( d[x] > d[start] ) {

			start = x;

		}

	}

	end = start;

	for ( auto x : w ) {

		d[x] = -1;

	}

	d[start] = 0;

	diameter[start] = start;

	q.push( start );

	while ( !q.empty() ) {

		int x = q.front();
		q.pop();

		for ( auto y : adj[x] ) {

			if ( d[y.first] == -1 ) {

				diameter[y.first] = x;

				d[y.first] = d[x] + y.second;

				q.push( y.first );

			}

		}

		if ( d[x] > d[end] ) {

			end = x;

		}

	}

	dist = 0;

	answer1 = d[end];

	mxd = max( mxd, d[end] );

	while ( end != start ) {

		answer1 = min( answer1, max( dist, d[end] ) );

		dist += d[end] - d[diameter[end]];

		end = diameter[end];

	}

	return answer1;

}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

	n = N, m = M, d1 = L;

	visited.resize( n, false );

	adj.resize( n );

	d.resize( n, -1 );
	diameter.resize( n );

	for ( int i = 0; i < m; i++ ) {

		adj[A[i]].push_back( { B[i], T[i] } );
		adj[B[i]].push_back( { A[i], T[i] } );

	}

	for ( int i = 0; i < n; i++ ) {

		if ( visited[i] == false ) {

			bfs( i );

		}

	}

	vector <int> medians;

	for ( int i = 0; i < (int)v.size(); i++ ) {

		medians.push_back( median( v[i] ) );

	}

	sort ( medians.rbegin(), medians.rend() );

	answer = mxd;

	if ( medians.size() > 1 ) {

		answer = max( answer, medians[0] + medians[1] + d1 );

	}

	if ( medians.size() > 2 ) {

		answer = max( answer, medians[1] + medians[2] + d1 + d1 );

	}

	return answer;

}
/*
#include <stdio.h>
#include <stdlib.h>
//#include "dreaming.h"

#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_N 100000

static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];

int main() {
	int N, M, L, i;
	int res;

	FILE *f = fopen("dreaming.in", "r");
	if (!f)
		fail("Failed to open input file.");

	res = fscanf(f, "%d%d%d", &N, &M, &L);
	for (i = 0; i < M; i++)
		res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
	fclose(f);

	int answer = travelTime(N, M, L, A, B, T);
	printf("%d\n", answer);

	return 0;
}
*/

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