제출 #456210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456210		sean617	경주 (Race) (IOI11_race)	C++98	43 / 100	393 ms	37996 KiB

race

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define SZ 200005
#define A 1000005
#include "race.h"

using namespace std;
int n, k, mn, M = 1e9, s[A], sz[SZ];
bool v2[SZ];
vector<int> a[SZ], b[SZ];
queue<int> qu;


int gs(int p, int q) {
	int i, t;
	sz[p] = 1;
	for (i = 0; i < a[p].size(); i++) {
		t = a[p][i];
		if (t == q || v2[t]) continue;
		sz[p] += gs(t, p);
	}
	return sz[p];
}

int gc(int p, int q, int nn) {
	int i, t;
	for (i = 0; i < a[p].size(); i++) {
		t = a[p][i];
		if (t != q && !v2[t] && sz[t] *2 > nn) return gc(t, p, nn);
	}
	return p;
}

void g(int p, int q, int w, int cnt) {
	int i, t;
	if (w > k) return;
	mn = min(mn, cnt + s[k - w]);
	for (i = 0; i < a[p].size(); i++) {
		t = a[p][i];
		if (t == q || v2[t]) continue;
		g(t, p, w + b[p][i], cnt + 1);
	}
	if (s[w] > cnt) {
		s[w] = cnt;
		qu.push(w);
	}
}

void f(int p) {
	int i, t, cen;
	gs(p, -1);
	cen = gc(p, -1, sz[p]);
	v2[cen] = 1;
	while (!qu.empty()) {
		t = qu.front(); qu.pop();
		s[t] = M;
	}
	s[0] = 0;
	for (i = 0; i < a[cen].size(); i++) {
		t = a[cen][i];
		if (v2[t]) continue;
		g(t, -1, b[cen][i], 1);
	}
	for (i = 0; i < a[cen].size(); i++) {
		t = a[cen][i];
		if (v2[t]) continue;
		f(t);
	}
}

int best_path(int NN, int KK, int H[][2], int L[])
{
	int i, t1, t2, t3;
	n = NN;
	k = KK;
	for (i = 0; i < n - 1; i++) {
		t1 = H[i][0];
		t2 = H[i][1];
		t3 = L[i];
		a[t1].push_back(t2);
		b[t1].push_back(t3);
		a[t2].push_back(t1);
		b[t2].push_back(t3);
	}
	mn = M;
	for (i = 0; i <= k; i++) s[i] = M;
	f(0);
	if (mn == M) mn = -1;

  return mn;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int gs(int, int)':
race.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (i = 0; i < a[p].size(); i++) {
      |              ~~^~~~~~~~~~~~~
race.cpp: In function 'int gc(int, int, int)':
race.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (i = 0; i < a[p].size(); i++) {
      |              ~~^~~~~~~~~~~~~
race.cpp: In function 'void g(int, int, int, int)':
race.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (i = 0; i < a[p].size(); i++) {
      |              ~~^~~~~~~~~~~~~
race.cpp: In function 'void f(int)':
race.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (i = 0; i < a[cen].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~
race.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (i = 0; i < a[cen].size(); i++) {
      |              ~~^~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57