Submission #276051

#	Time	Username	Problem	Language	Result	Execution time	Memory
276051		abyyskit	Race (IOI11_race)	C++14	9 / 100	3096 ms	29392 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back

int ANS;
int TIME;
int K;

struct node{
	vector<int> e;
	vector<int> w;
	int start = -1;
	int end;
	vector<int> l = vector<int>(19);
	int p = 0;
	int h;
	
};
vector<node> g;

void dfs(int start, int height){
	g[start].start = TIME;
	g[start].h = height;
	TIME++;
	FOR(i, 0, g[start].e.size()){
		int nex = g[start].e[i];
		if (g[nex].start == -1){
			g[nex].l[0] = start;
			g[nex].p = g[start].p + g[start].w[i];
			dfs(nex, height + 1);	
		}
	}
	g[start].end = TIME;
	TIME++;
}

void setup_LCA(){
	g[0].l[0] = 0;
	FOR(i, 0, g.size()){
		FOR(j, 1, g[i].l.size()){
			g[i].l[j] = g[g[i].l[j - 1]].l[j - 1];
		}
	}
}

int LCA(int a, int b){
	int cur = a;
	//cout << a << " " << b << "\n";
	for (int i = g[a].l.size() - 1; i >= 0; --i){
		int nex = g[cur].l[i];
		if (!(g[nex].start <= g[b].start and g[b].start <= g[nex].end)){
			cur = nex;
		}
	//	cout << "  step: " << i << " looked at " << nex << " now at " << cur << "\n"; 
	}
	int tmp = 0;
//	cout << "  " << g[cur].start << " " << g[b].start << " " << g[cur].end << "\n";
	while (!(g[cur].start <= g[b].start and g[b].start <= g[cur].end)){
		cur = g[cur].l[0];
//		cout << "  here\n";
		tmp++;
		if (tmp > 2){
	//		cout << "suicide\n";
	//		cout << (1/0) << "\n";
		}
	}
//	cout << "LCA(" << a << ", " << b << ") = " << cur << ", ";
	return cur;
}

int solve(int a, int b){
	int c = LCA(a, b);
	int dis = g[a].h + g[b].h - 2*g[c].h;
	int odis = g[a].p + g[b].p - 2*g[c].p;
//	cout << "dis(" << a << ", " << b << ") = " << dis << ", ";
//	cout << "odis(" << a << ", " << b << ") = " << odis << ", ";
//	cout << "\n";
	if (odis == K){
		return dis;
	}
	else{
		return g.size() + 1;
	}
}



int best_path(int N, int k, int H[][2], int L[]){
  	ANS = N + 1;
	K = k;
	TIME = 0;
	g.resize(N);
	FOR(i, 0, N-1){
		g[H[i][0]].e.pb(H[i][1]);
		g[H[i][0]].w.pb(L[i]);
		g[H[i][1]].e.pb(H[i][2]);
		g[H[i][1]].w.pb(L[i]);
	}

	dfs(0, 0);
	setup_LCA();
	FOR(i, 0, N){
		FOR(j, i + 1, N){
			ANS = min(ANS, solve(i, j));
		}
	}
	if (ANS == N + 1){
		ANS = -1;
	}
	return ANS;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   27 |  FOR(i, 0, g[start].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~~~           
race.cpp:27:2: note: in expansion of macro 'FOR'
   27 |  FOR(i, 0, g[start].e.size()){
      |  ^~~
race.cpp: In function 'void setup_LCA()':
race.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   41 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
race.cpp:41:2: note: in expansion of macro 'FOR'
   41 |  FOR(i, 0, g.size()){
      |  ^~~
race.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   42 |   FOR(j, 1, g[i].l.size()){
      |       ~~~~~~~~~~~~~~~~~~~              
race.cpp:42:3: note: in expansion of macro 'FOR'
   42 |   FOR(j, 1, g[i].l.size()){
      |   ^~~

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