Submission #41083

#	Time	Username	Problem	Language	Result	Execution time	Memory
41083		comtalyst	Race (IOI11_race)	C++14	21 / 100	235 ms	28028 KiB

race

/*
 *	Task: ioi11_race
 *	Lang: C/C++11
 *	Site: oj.uz
 *	Last Update: 12/2/2018
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
----------------------------
Learned : 
Bugs found & solved :
Optimizations :
----------------------------
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (int)(1e9+5)
#define MIN (int)(-1e9-5)
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

//int tmp[200005][2],tmp2[200005];

vector<pair<int,int>> adl[200005];
umap<int,int> s[200005];
int ls[200005],sid[200005],lv[200005],sc,n,m,mn=MAX;
void solve(int x,int f){
	int i,y,id,v,need,w;
	pair<int,int> mx={0,0};
	lv[x] = lv[f]+1;
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		if(y == f) continue;
		solve(y,x);
		id = sid[y];
		mx = max(mx,{s[id].size(),y});
	}
//	printf(">>>>>>>>> %d from %d\n",x,f);
	if(mx.x){
		sid[x] = sid[mx.y];
	}
	else{
		sid[x] = ++sc;
		mx.y = 0;
	}
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		if(y == f || y == mx.y) continue;
		id = sid[y];
		while(!s[id].empty()){
			v = (*s[id].begin()).x + ls[id];
			need = m-v-ls[sid[x]];
//			printf(":: %d\n",v);
			if(s[sid[x]][need]){
//				printf("<<<<< %d\n",s[sid[x]][need]+(*s[id].begin()).y-lv[x]*2);
				mn = min(mn,s[sid[x]][need]+(*s[id].begin()).y-lv[x]*2);
			}
			else{
				s[sid[x]].erase(need);
			}
			if(s[sid[x]][v-ls[sid[x]]]){
				s[sid[x]][v-ls[sid[x]]] = min(s[sid[x]][v-ls[sid[x]]],(*s[id].begin()).y);
			}
			else{
				s[sid[x]][v-ls[sid[x]]] = (*s[id].begin()).y;
			}
			s[id].erase(s[id].begin());
		}
	}
	for(i = 0; i < adl[x].size(); i++){
		y = adl[x][i].x;
		w = adl[x][i].y;
		if(y == f){
			break;
		}
	}
	need = m-w-ls[sid[x]];
	if(s[sid[x]][need]){
		mn = min(mn,s[sid[x]][need]-lv[f]);
	}
	else{
		s[sid[x]].erase(need);
	}
	ls[sid[x]] += w;
	s[sid[x]][w - ls[sid[x]]] = lv[x];
}

int best_path(int _n,int _m,int _edl[][2],int _edw[]){			// f*ck you 0-based idx
	int i,j;

	n = _n;
	m = _m;
	for(i = 0; i < n-1; i++){
		adl[_edl[i][0]+1].emplace_back(_edl[i][1]+1,_edw[i]);
		adl[_edl[i][1]+1].emplace_back(_edl[i][0]+1,_edw[i]);
	}
	solve(1,0);
	if(mn != MAX){
		return mn;
	}
	else{
		return -1;
	}
}

/*main(){
	int t,i,j,k,_n,_m;
	
	scanf("%d %d",&_n,&_m);
	for(i = 0; i < _n-1; i++){
		scanf("%d %d",&tmp[i][0],&tmp[i][1]);
	}
	for(i = 0; i < _n-1; i++){
		scanf("%d",&tmp2[i]);
	}
	printf(">> %d\n",best_path(_n,_m,tmp,tmp2));

	return 0;	
}*/

Compilation message (stderr)

race.cpp: In function 'void solve(int, int)':
race.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:103:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
race.cpp: In function 'void solve(int, int)':
race.cpp:91:10: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
  need = m-w-ls[sid[x]];
         ~^~

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