Submission #276119

#	Time	Username	Problem	Language	Result	Execution time	Memory
276119		abyyskit	Race (IOI11_race)	C++14	21 / 100	3083 ms	27104 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;
long long K;

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

void dfs(int start, int height){
	g[start].start = TIME;
	g[start].h = height;
	g[start].vis = true;
	TIME++;
	FOR(i, 0, g[start].e.size()){
		int nex = g[start].e[i];
		if (!g[nex].vis){
			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;
	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;
		}
	}
	int tmp = 0;
	while (!(g[cur].start <= g[b].start and g[b].start <= g[cur].end)){
		cur = g[cur].l[0];
		tmp++;
	}
//	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;
	long long 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;
	}
}

void reset(){
	FOR(i, 0, g.size()){
		g[i].vis = false;
	}
}

void dfs2(int start, int dis, int length){
	g[start].vis = true;
	if (length == K){
		ANS = min(ANS, dis);
	}
	FOR(i, 0, g[start].e.size()){
		int nex = g[start].e[i];
		if (!g[nex].vis){
			dfs2(nex, dis + 1, length +  g[start].w[i]);
		}
	}

}

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][0]);
		g[H[i][1]].w.pb(L[i]);
	}

	dfs(0, 0);
	setup_LCA();
	FOR(i, 0, N){
	//	reset();
	//	dfs2(i, 0, 0);
		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)
......
   28 |  FOR(i, 0, g[start].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~~~           
race.cpp:28:2: note: in expansion of macro 'FOR'
   28 |  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)
......
   42 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
race.cpp:42:2: note: in expansion of macro 'FOR'
   42 |  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)
......
   43 |   FOR(j, 1, g[i].l.size()){
      |       ~~~~~~~~~~~~~~~~~~~              
race.cpp:43:3: note: in expansion of macro 'FOR'
   43 |   FOR(j, 1, g[i].l.size()){
      |   ^~~
race.cpp: In function 'void reset()':
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)
......
   82 |  FOR(i, 0, g.size()){
      |      ~~~~~~~~~~~~~~                    
race.cpp:82:2: note: in expansion of macro 'FOR'
   82 |  FOR(i, 0, g.size()){
      |  ^~~
race.cpp: In function 'void dfs2(int, 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)
......
   92 |  FOR(i, 0, g[start].e.size()){
      |      ~~~~~~~~~~~~~~~~~~~~~~~           
race.cpp:92:2: note: in expansion of macro 'FOR'
   92 |  FOR(i, 0, g[start].e.size()){
      |  ^~~

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