oj.uz

Submission #132987

# Submission time Handle Problem Language Result Execution time Memory
132987 2019-07-20T03:30:02 Z wilwxk Race (IOI11_race) C++14
0 / 100
 15 ms 14456 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e5+5;
const int MAXX=1e6+5;
vector<int> g[MAXN], pes[MAXN];
int n, respf;
ll x;

class solution {
public:
	int resp=MAXN;
	void init() {
		tam[n]=0;
		memset(prof, 0, sizeof(prof));
		fill(best, best+MAXX-2, MAXN);
		best[0]=0;
		solve(0, 1);
	}
	void solve(int cur, int k) {
		basic_scan(cur, cur);
		cur=find_centroid(cur, cur, tam[cur]);
		prof[cur]=k;
		
		// printf(">> %d <<\n", cur);

		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; ll peso=pes[cur][i];
			adv_scan(viz, cur, 1, peso, 0);
			adv_scan(viz, cur, 1, peso, 1);
		}
		adv_scan(cur, cur, 0, 0, -1);

		for(auto viz : g[cur]) {
			if(prof[viz]) continue;
			solve(viz, k+1);
		}
	}

private:
	int tam[MAXN], prof[MAXN];
	int best[MAXX];
	void basic_scan(int cur, int p) {
		tam[cur]=1;
		for(auto viz : g[cur]) {
			if(viz==p||prof[viz]) continue;
			basic_scan(viz, cur);
			tam[cur]+=tam[viz];
		}
	}
	void adv_scan(int cur, int p, int d, ll dd, int k) {
		if(dd>x) return;
		if(k==0) resp=min(resp, d+best[x-dd]);
		else if(k==1) best[dd]=min(best[dd], d);
		else best[dd]=MAXN;
		for(int i=0; i<g[cur].size(); i++) {
			int viz=g[cur][i]; ll peso=pes[cur][i];
			if(viz==p||prof[viz]) continue;
			adv_scan(viz, cur, d+1, dd+peso, k);
		}
	}
	int find_centroid(int cur, int p, int val) {
		int grande=n;
		for(auto viz : g[cur]) if(viz!=p&&!prof[viz]&&tam[viz]>tam[grande]) grande=viz;
		if(tam[grande]*2<=val) return cur;
		return find_centroid(grande, cur, val);
	}

};

int best_path(int N, int K, int H[][2], int L[])
{
	n=N; x=K;
	for(int i=0; i<n-1; i++) {
		int a=H[i][0]; int b=H[i][1];
		g[a].push_back(b); pes[a].push_back(L[i]);
		g[b].push_back(a); pes[b].push_back(L[i]);
	}

	solution sol;
	sol.init();

	respf=sol.resp;
	if(respf>=n) respf=-1;

	return respf;
}

Compilation message

race.cpp: In member function 'void solution::solve(int, int)':
race.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
race.cpp: In member function 'void solution::adv_scan(int, int, int, ll, int)':
race.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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